Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef unsigned long long ll;
- #define MAX 10000
- #define all(v) v.begin(),v.end()
- ll N=5*1e6+2,m;
- vector<bool>isprime(N);
- vector<ll>phi;
- vector<ll>prime;
- void seive()
- {
- ll i,n=N,j;
- isprime[1]=1;
- isprime[0]=1;
- for(i=4; i<=n; i+=2)
- isprime[i]=1;
- for(i=3; i*i<=n; i+=2)
- {
- if(isprime[i]==0)
- for(j=i*i; j<=n; j+=i)
- isprime[j]=1;
- }
- for(i=0; i<=n; i++)
- {
- if(isprime[i]==0)
- prime.push_back(i);
- }
- }
- void solve()
- {
- ll i,j;
- for(i=0; i<N; i++)
- phi.push_back(i);
- for(i=0; i<prime.size(); i++)
- {
- for(j=prime[i]; j<N; j+=prime[i])
- {
- phi[j]*=(prime[i]-1);
- phi[j]/=prime[i];
- }
- }
- }
- int main()
- {
- seive();
- solve();
- // freopen("input.txt","r",stdin);
- // freopen("output.txt","w",stdout);
- ll test,t,i;
- vector<ll>a(N+8,0);
- for(i=2; i<N; i++)
- a[i]=phi[i]*phi[i]+a[i-1];
- scanf("%llu",&test);
- for(t=1; t<=test; t++)
- {
- ll a1,b;
- scanf("%llu %llu",&a1,&b);
- a1--;
- printf("Case %llu: %llu\n",t,a[b]-a[a1]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement