Submission #3791433


Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
namespace Fact{
	long f[4000000];
	long rf[4000000];
	long pow(long N,long K){
		if(K == 0){
			return 1;
		}
		else if(K % 2 == 0){
			long t = pow(N,K/2);
			return t*t%mod;
		}
		else{
			return N*pow(N,K-1)%mod;
		}
	}
	void Fact(int N){
		for(int i=0;i<N+1;i++){
			if(i == 0){
				f[i] = 1;
			}
			else{
				f[i] = (f[i-1]*i)%mod;
			}
		}
		for(int i=N;i>=0;i--){
			if(i == N){
				rf[i] = pow(f[N],mod-2);
			}
			else{
				rf[i] = rf[i+1]*(i+1)%mod;
			}
		}
	}
	long GetFact(int N){
		return f[N];
	}
	long GetPerm(int N,int R){
		return f[N] * rf[N-R] % mod;
	}
	long GetConv(int N,int R){
		return ((f[N]*rf[R])%mod*rf[N-R])%mod;
	}
	long GetRev(int N){
		return rf[N] * f[N-1] % mod;
	}
}
int X[100000];
long ans[100000];
int L[100000];
int R[100000];
vector<int> prime;
int LowestPrimeFactor[100001];
int order[100000];
int pn[100000];
long c;
void Plus(int x){
	while(x != 1){
		int p = LowestPrimeFactor[x];
		c *= pn[p]+2;
		c %= mod;
		c *= Fact::GetRev(pn[p]+1);
		c %= mod;
		pn[p]++;
		x /= p;
	}
}
void Minus(int x){
	while(x != 1){
		int p = LowestPrimeFactor[x];
		c *= pn[p];
		c %= mod;
		c *= Fact::GetRev(pn[p]+1);
		c %= mod;
		pn[p]--;
		x /= p;
	}
}
bool compare(int x,int y){
	if(L[x] / 300 != L[y] / 300){
		return L[x] / 300 < L[y] / 300;
	}
	return R[x] < R[y];
}
void Calc(){
	int N = rei();
	int Q = rei();
	Fact::Fact(3600000);
	for(int i=0;i<N;i++){
		X[i] = rei();
	}
	for(int i=0;i<Q;i++){
		L[i] = rei()-1;
		R[i] = rei()-1;
		order[i] = i;
	}
	for(int i=2;i<=100000;i++){
		if(LowestPrimeFactor[i] == 0){
			LowestPrimeFactor[i] = i;
			prime.push_back(i);
		}
		for(int j=0;j!=prime.size() && prime[j]<=LowestPrimeFactor[i];j++){
			if(i*prime[j] > 100000){
				break;
			}
			LowestPrimeFactor[i*prime[j]] = prime[j];
		}
	}
	sort(order,order+Q,compare);
	int l = 0;
	int r = -1;
	c = 1;
	for(int q=0;q<Q;q++){
		while(r < R[order[q]]){
			Plus(X[++r]);
		}
		while(l > L[order[q]]){
			Plus(X[--l]);
		}
		while(r > R[order[q]]){
			Minus(X[r--]);
		}
		while(l < L[order[q]]){
			Minus(X[l++]);
		}
		ans[order[q]] = c;
	}
	for(int q=0;q<Q;q++){
		cout << ans[q] << endl;
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Submission Info

Submission Time
Task B - ニワンゴくんの約数
User leign
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3117 Byte
Status TLE
Exec Time 2656 ms
Memory 64768 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 2
AC × 16
TLE × 8
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 642 ms 64768 KB
02.txt TLE 2656 ms 63872 KB
03.txt AC 564 ms 64640 KB
04.txt AC 2179 ms 64640 KB
05.txt AC 833 ms 64384 KB
06.txt TLE 2656 ms 63488 KB
07.txt AC 1250 ms 64384 KB
08.txt TLE 2656 ms 63488 KB
09.txt AC 554 ms 64768 KB
10.txt AC 2317 ms 64768 KB
11.txt AC 1257 ms 64384 KB
12.txt TLE 2656 ms 63488 KB
13.txt AC 452 ms 64128 KB
14.txt AC 1189 ms 64000 KB
15.txt AC 1889 ms 64256 KB
16.txt TLE 2656 ms 63488 KB
17.txt AC 962 ms 64384 KB
18.txt TLE 2656 ms 63488 KB
19.txt AC 1431 ms 64384 KB
20.txt TLE 2656 ms 63488 KB
21.txt AC 882 ms 64384 KB
22.txt TLE 2656 ms 63488 KB
s1.txt AC 61 ms 62208 KB
s2.txt AC 60 ms 62208 KB