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 |
|
|
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 |