#include<stdio.h>
#include<memory.h>
#define min2(a,b) ((a)>(b)?(b):(a))
#define mod 1000000007
#define MX 21000000
using namespace std;
typedef long long lld;
int se[11111][2];
lld phi[1000002], top[1000002], cnt, n, gap[11111], mx, gop=1, zcn, dap;
int ix[MX], pv[MX];
void make(int it){
int i, j, a;
for(i=1; i*i<=se[it][1]; i++)ix[cnt]=it, pv[cnt]=top[i], top[i]=cnt++;
j=se[it][0]/i, i=se[it][1]/i;
for(; i>=1;){ // 몫 = 3
if(j==0){
a=se[it][1]/i;
ix[cnt]=it, pv[cnt]=top[a];
i--;
}
else{
a=min2(se[it][0]/j, se[it][1]/i);
ix[cnt]=it, pv[cnt]=top[a];
if(se[it][0]/j == se[it][1]/i)i--, j--;
else if(se[it][0]/j > se[it][1]/i)i--;
else j--;
}
top[a]=cnt++;
}
}
lld pow(lld a, lld b){
lld v = a, ret = 1;
for (;b;b>>=1,v=v*v%mod) if(b&1) ret=ret*v%mod;
return ret;
}
int main(){
lld i, j, p, q;
scanf("%lld", &n), zcn=n;
memset(top, -1, sizeof(top));
for(i=0; i<n; i++){
scanf("%d%d", &se[i][0], &se[i][1]), se[i][0]--;
make(i);
if(se[i][1]>mx)mx=se[i][1];
}
phi[1]=1;
for(i=2; i<=mx; i++){
if(phi[i]==0){
phi[i]=i-1;
if(i>1000)continue;
for(j=i*i; j<=mx; j+=i)phi[j]=i;
}
else{
p=phi[i];
if(i%(p*p)==0)phi[i]=p*phi[i/p];
else phi[i]=(p-1)*phi[i/p];
}
}
for(i=mx; i>=1; i--){
for(j=top[i]; j>=0; j=pv[j]){
p=ix[j], q=se[p][1]/i-se[p][0]/i;
if(gap[p]==0)zcn--;
else gop=(gop*pow(gap[p],mod-2))%mod;
gap[p]=q;
if(q==0)zcn++;
else gop=(gop*q)%mod;
}
if(zcn==0){
dap+=gop*phi[i]%mod;
if(dap>=mod)dap-=mod;
}
}
printf("%lld", dap);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
180948 KB |
Output is correct |
| 2 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 3 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 4 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 5 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 6 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 7 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 8 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 9 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 10 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 11 |
Correct |
48 ms |
180948 KB |
Output is correct |
| 12 |
Correct |
48 ms |
180948 KB |
Output is correct |
| 13 |
Correct |
48 ms |
180948 KB |
Output is correct |
| 14 |
Correct |
48 ms |
180948 KB |
Output is correct |
| 15 |
Correct |
44 ms |
180948 KB |
Output is correct |
| 16 |
Correct |
8 ms |
180948 KB |
Output is correct |
| 17 |
Correct |
32 ms |
180948 KB |
Output is correct |
| 18 |
Correct |
40 ms |
180948 KB |
Output is correct |
| 19 |
Correct |
16 ms |
180948 KB |
Output is correct |
| 20 |
Correct |
28 ms |
180948 KB |
Output is correct |
| 21 |
Correct |
48 ms |
180948 KB |
Output is correct |
| 22 |
Correct |
52 ms |
180948 KB |
Output is correct |
| 23 |
Correct |
52 ms |
180948 KB |
Output is correct |
| 24 |
Correct |
48 ms |
180948 KB |
Output is correct |
| 25 |
Correct |
48 ms |
180948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
180948 KB |
Output is correct |
| 2 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 3 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 4 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 5 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 6 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 7 |
Correct |
4 ms |
180948 KB |
Output is correct |
| 8 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 9 |
Correct |
4 ms |
180948 KB |
Output is correct |
| 10 |
Correct |
0 ms |
180948 KB |
Output is correct |
| 11 |
Correct |
696 ms |
180948 KB |
Output is correct |
| 12 |
Correct |
692 ms |
180948 KB |
Output is correct |
| 13 |
Correct |
696 ms |
180948 KB |
Output is correct |
| 14 |
Correct |
696 ms |
180948 KB |
Output is correct |
| 15 |
Correct |
692 ms |
180948 KB |
Output is correct |
| 16 |
Correct |
64 ms |
180948 KB |
Output is correct |
| 17 |
Correct |
88 ms |
180948 KB |
Output is correct |
| 18 |
Correct |
3116 ms |
180948 KB |
Output is correct |
| 19 |
Correct |
3904 ms |
180948 KB |
Output is correct |
| 20 |
Correct |
2700 ms |
180948 KB |
Output is correct |
| 21 |
Correct |
1420 ms |
180948 KB |
Output is correct |
| 22 |
Execution timed out |
4000 ms |
180944 KB |
Program timed out |
| 23 |
Halted |
0 ms |
0 KB |
- |
