#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;
freopen("input.txt","r",stdin);
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
0 ms |
176992 KB |
open (syscall #2) was called by the program (disallowed syscall) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
