UVa11876 - N + NOD (N)

#include <cstdio>#include <cstring>#include <map>#include <cmath>#include <algorithm>usingnamespacestd;
constintN=1100;
constintM=65000;;
constintP=200;
constintMAX=1000001;
boolvis[N];
inta, b;
intvPrime[P], primeCnt;
intNi[M], NiCnt;
intans[MAX];
voidinput();
intsolve();
voidsieve_of_sundaram();
intcal(intn);
voidinit();
intmain()
{
#ifndef ONLINE_JUDGEfreopen("d:\\OJ\\uva_in.txt", "r", stdin);
#endifinit();
intt;
scanf("%d", &t);
for (inti=1; i<=t; i++) {
input();
printf("Case %d: %d\n", i, solve());
    }
return0;
}
voidsieve_of_sundaram()
{
intm= (int)sqrt(N/2);
memset(vis, false, sizeof(vis));
for (inti=1; i<m; i++) {
if (vis[i]) continue;
for (intj=2*i* (i+1), k=2*i+1; j<N; j+=k) {
vis[j] =true;
        }
    }
primeCnt=0;
vPrime[primeCnt++] =2;
for (inti=1; i<N/2; i++) {
if (!vis[i]) vPrime[primeCnt++] =2*i+1;
    }
}
intcal(intn)
{
map<int, int>m;
for (inti=0; i<primeCnt; i++) {
if (n<vPrime[i]) break;
if (n%vPrime[i] ==0) {
intcnt=0;
while (n%vPrime[i] ==0) {
cnt++; 
n/=vPrime[i];
            }
m[vPrime[i]] =cnt;
        }
    }
if (n!=1) m[n] =1;
intans=1;
for (map<int, int>::iteratorit=m.begin(); it!=m.end(); it++) {
ans*= (it->second+1);
    }
returnans;
}
voidinit()
{
sieve_of_sundaram();
NiCnt=0;
Ni[NiCnt++] =1;
ans[0] =0;
ans[1] =1;
while (true) {
intn=Ni[NiCnt-1];
intm=n+cal(n);
if (m>1000000) {
fill(&ans[n], &ans[1000001], NiCnt);
break;
        }
fill(&ans[n], &ans[m], NiCnt);
Ni[NiCnt++] =m;
    }
}
voidinput()
{
scanf("%d%d", &a, &b);
}
intsolve()
{
returnans[b] -ans[a-1];
}