#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 n, se[11111][2], gap[11111];
int phi[1000002], top[1000002], inv[1000002], cnt, 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++;
}
}
int pow(int a, int b){
int v = a, ret = 1;
for (;b;b>>=1,v=(lld)v*v%mod) if(b&1) ret=(lld)ret*v%mod;
return ret;
}
int main(){
int i, j, p, q;
scanf("%d", &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=1; i<=mx; i++)inv[i]=pow(i,mod-2);
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=((lld)gop*inv[gap[p]])%mod;
gap[p]=q;
if(q==0)zcn++;
else gop=((lld)gop*q)%mod;
}
if(zcn==0){
dap+=(lld)gop*phi[i]%mod;
if(dap>=mod)dap-=mod;
}
}
printf("%d", dap);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 2 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 3 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 4 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 5 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 6 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 7 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 8 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 9 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 10 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 11 |
Correct |
256 ms |
177000 KB |
Output is correct |
| 12 |
Correct |
256 ms |
177000 KB |
Output is correct |
| 13 |
Correct |
260 ms |
177000 KB |
Output is correct |
| 14 |
Correct |
248 ms |
177000 KB |
Output is correct |
| 15 |
Correct |
248 ms |
177000 KB |
Output is correct |
| 16 |
Correct |
28 ms |
177000 KB |
Output is correct |
| 17 |
Correct |
212 ms |
177000 KB |
Output is correct |
| 18 |
Correct |
232 ms |
177000 KB |
Output is correct |
| 19 |
Correct |
76 ms |
177000 KB |
Output is correct |
| 20 |
Correct |
128 ms |
177000 KB |
Output is correct |
| 21 |
Correct |
260 ms |
177000 KB |
Output is correct |
| 22 |
Correct |
256 ms |
177000 KB |
Output is correct |
| 23 |
Correct |
264 ms |
177000 KB |
Output is correct |
| 24 |
Correct |
252 ms |
177000 KB |
Output is correct |
| 25 |
Correct |
256 ms |
177000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 2 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 3 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 4 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 5 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 6 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 7 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 8 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 9 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 10 |
Correct |
0 ms |
177000 KB |
Output is correct |
| 11 |
Correct |
400 ms |
177000 KB |
Output is correct |
| 12 |
Correct |
400 ms |
177000 KB |
Output is correct |
| 13 |
Correct |
388 ms |
177000 KB |
Output is correct |
| 14 |
Correct |
388 ms |
177000 KB |
Output is correct |
| 15 |
Correct |
396 ms |
177000 KB |
Output is correct |
| 16 |
Correct |
184 ms |
177000 KB |
Output is correct |
| 17 |
Correct |
240 ms |
177000 KB |
Output is correct |
| 18 |
Correct |
1184 ms |
177000 KB |
Output is correct |
| 19 |
Correct |
1264 ms |
177000 KB |
Output is correct |
| 20 |
Correct |
736 ms |
177000 KB |
Output is correct |
| 21 |
Correct |
660 ms |
177000 KB |
Output is correct |
| 22 |
Correct |
2308 ms |
177000 KB |
Output is correct |
| 23 |
Correct |
2396 ms |
177000 KB |
Output is correct |
| 24 |
Correct |
1844 ms |
177000 KB |
Output is correct |
| 25 |
Correct |
1864 ms |
177000 KB |
Output is correct |
