lightoj1007

CODE

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 5e6+5;
unsigned long long vis[N];
void phi()
{
        memset(vis,0,sizeof(vis));
        vis[1]=1;
        for(int i=2;i<N;i++)if(!vis[i])
        {
                for(int j=i;j<N;j+=i)
                {
                        if(!vis[j])vis[j]=j;
                         vis[j]=vis[j]*(i-1)/i;
                }
        }
        for(int i=2;i<N;i++)
        {
                vis[i]=vis[i-1]+vis[i]*vis[i];
        }

}

int main()
{
        phi();
        int t;
        cin >> t;
        for(int nCase=1;nCase<=t;nCase++)
        {
                int a,b;
                scanf("%d %d",&a,&b);
                //cin >> a >> b;
                //cout << "Case "<<nCase<<": ";
                //cout << vis[b]-vis[a-1]<<endl;
                printf("Case %d: %llu\n",nCase,vis[b]-vis[a-1]);
        }
        return 0;
}