UVa10484 - Divisibility of Factors(数论)

#include <cstdio>#include <vector>#include <cstring>#include <cmath>#include <map>#include <cstdlib>usingnamespacestd;
constintN=50000;
vector<int>vPrime;
boolvis[N];
intn, d;
voidcalc(intn, map<int, int>&m);
voidsieve_of_sundaram();
boolinput();
voidsolve();
intmain()
{
#ifndef ONLINE_JUDGEfreopen("e:\\uva_in.txt", "r", stdin);
#endifsieve_of_sundaram();
while (input()) {
solve();
    }
return0;
}
boolinput()
{
scanf("%d%d", &n, &d);
if (n==0&&d==0) returnfalse;
d=abs(d);
returntrue;
}
voidsolve()
{
if (n==0&&d==1) {
printf("1\n");
return;
    }
map<int, int>nmap, dmap;
for (inti=2; i<=n; i++) calc(i, nmap);
calc(d, dmap);
for (map<int, int>::iteratorit=dmap.begin(); it!=dmap.end(); it++) {
if (nmap.count(it->first) ==0) {
printf("0\n");
return;
        }
if (nmap[it->first] <it->second) {
printf("0\n");
return;
        }
nmap[it->first] -=it->second;
    }
longlongans=1;
for (map<int, int>::iteratorit=nmap.begin(); it!=nmap.end(); it++) {
ans*= (nmap[it->first] +1);
    }
printf("%lld\n", ans);
}
voidsieve_of_sundaram()
{
memset(vis, false, sizeof(vis));
intm= (int)sqrt(N/2);
for (inti=1; i<m; i++) {
if (vis[i]) continue;
for (intk=2*i+1, j=2*i* (i+1); j<N; j+=k) {
vis[j] =true;
        }
    }
vPrime.push_back(2);
for (inti=1; i<N/2; i++) {
if (!vis[i]) vPrime.push_back(2*i+1);
    }
}
voidcalc(intn, map<int, int>&m)
{
for (size_ti=0; i<vPrime.size(); i++) {
intcnt=0;
if (n<vPrime[i]) break;
if (n%vPrime[i] ==0) {
while (n%vPrime[i] ==0) {
n/=vPrime[i];
cnt++;
            }
m[vPrime[i]] +=cnt;
        }
    }
if (n!=1) m[n] +=1;
}