3315 - 双亲数
时间限制 : 1 秒
内存限制 : 128 MB
Dizzy是一名数学爱好者，他对数字的着迷到了疯狂的程度。
我们以d = gcd(a, b)表示a、b的最大公约数，Dizzy执著的认为，这样亲密的关系足可以用双亲来描述，此时，我们称有序数对(a, b)为d的双亲数。
与现实生活中的双亲不太相同的是，对于同一个d，他的双亲太多了 >_<。
比如，(4, 6), (6, 4), (2, 100)都是2的双亲数。
于是一个这样的问题摆在眼前，对于0 < a <= A, 0 < b <= B，有多少有序数对(a, b)是d的双亲数？
题目输入
输入文件只有一行，三个正整数A、B、d (d <= A, B)，意义如题所示。
题目输出
输出一行一个整数，给出满足条件的双亲数的个数。
输入/输出样例
输入格式
5 5 2
输出格式
3
C++解答
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn=2000001; long long a,b,d; long long f[maxn]; int main() { //freopen("parents.in","r",stdin); //freopen("parents.out","w",stdout); cin>>a>>b>>d; //a=a/d;b=b/d; if(a>b) { long long c; c=a;a=b;b=c; } for(int k=a;k>0;k--)//f[k]表示以k位公约数的最大数对 { f[k]=(a/k)*(b/k);//此时求得是以k位约数的对数 for(int i=2;i<=a/k;i++) f[k]=f[k]-f[k*i]; } cout<<f[d]<<endl; }