UVa10484 - Divisibility of Factors(数论)

简介: 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;
}
目录
相关文章
Mad Scientist (纯模拟题)
Mad Scientist 题目描述 Farmer John’s cousin Ben happens to be a mad scientist. Normally, this creates a good bit of friction at family gatherings, but it can occasionally be helpful, especially when Farmer John finds himself facing unique and unusual problems with his cows.
160 0
HDU-1017,A Mathematical Curiosity
HDU-1017,A Mathematical Curiosity
HDU 1017 A Mathematical Curiosity【水,坑】
A Mathematical Curiosity Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 41995    Accepted Su...
1113 0
Uva - 12050 Palindrome Numbers【数论】
题目链接:uva 12050 - Palindrome Numbers   题意:求第n个回文串 思路:首先可以知道的是长度为k的回文串个数有9*10^(k-1),那么依次计算,得出n是长度为多少的串,然后就得到是长度为多少的第几个的回文串了,有个细节注意的是, n计算完后要-1! 下面给出A...
852 0
数论 + 扩展欧几里得 - SGU 106. The equation
 The equation  Problem's Link   Mean:  给你7个数,a,b,c,x1,x2,y1,y2.求满足a*x+b*y=-c的解x满足x1= lx)    {        ans = min(rx,ry)-ma...
1195 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等