NOIP2009Hankson的趣味题
题目描述
Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson 正在思考一个有趣的问题。今天在课堂上，老师讲解了如何求两个正整数c1 和c2 的最大公约数和最小公倍数。现在Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x 满足：
1、x 和a0 的最大公约数是a1；
2、x 和b0 的最小公倍数是b1。
Hankson 的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x 的个数。请你帮助他编程求解这个问题。
输入格式
输入文件名为 son.in。第一行为一个正整数n，表示有n 组输入数据。接下来的n 行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0 能被a1 整除，b1 能被b0 整除。
输出格式
输出文件 son.out 共n 行。每组输入数据的输出结果占一行，为一个整数。对于每组数据：若不存在这样的 x，请输出0；若存在这样的 x，请输出满足条件的x 的个数；
样例数据 1
输入
2
41 1 96 288
95 1 37 1776
输出
6
2「说明」第一组输入数据，x 可以是9、18、36、72、144、288，共有6 个。第二组输入数据，x 可以是48、1776，共有2 个。
备注
「数据范围」
对于 50%的数据，保证有1≤a0，a1，b0，b1≤10000 且n≤100。
对于 100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000 且n≤2000。
题解
枚举答案i从1-根号b1，判断i以及b1/i是否合法。。。
这样可以得90分貌似
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans; int a0,a1,b0,b1; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } ll lcm(int a,int b) { return (ll)a*b/gcd(a,b); } void cal(int x) { if(gcd(x,a0)==a1) if(lcm(x,b0)==b)ans++; } int main() { n=read(); while(n--) { ans=0; a0=read();a1=read();b0=read();b1=read(); for(int i=1;i<=sqrt(b1);i++) if(b1%i==0) { cal(i); if(i*i!=b1)cal(b1/i); } printf("%d\n",ans); } return 0; } |
至于正解嘛
将b1的质因数分开考虑，然后用乘法原理计算方案
对于某个质因数x
设a0分解完得到c0个x，a1->c1，b0->c2，b1->c3，ans->t
那么依照题意，显然c0>=c1,c2<=c3
若c0>c1则t=c1
若c2<c3则t=c3
则若c0=c1且c2=c3 方案*=c3-c1+1，注意判无解
若c0>c1且c2>c3时只有c1=c3时方案*=1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define N 50000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,tot; int a0,b0,a1,b1,ans; int pri[50005]; bool mark[50005]; void getpri() { for(int i=2;i<=N;i++) { if(!mark[i])pri[++tot]=i; for(int j=1;j<=tot&&pri[j]*i<=N;j++) { mark[pri[j]*i]=1; if(pri[j]%i==0)break; } } } void solve(int x) { int c0=0,c1=0,c2=0,c3=0; while(a0%x==0){a0/=x;c0++;} while(a1%x==0){a1/=x;c1++;} while(b0%x==0){b0/=x;c2++;} while(b1%x==0){b1/=x;c3++;} if(c0==c1&&c2==c3) { if(c1<=c3)ans*=c3-c1+1; else ans=0; } else if(c0!=c1&&c2!=c3&&c1!=c3)ans=0; } int main() { getpri(); n=read(); while(n--) { ans=1; a0=read();a1=read();b0=read();b1=read(); for(int i=1;i<=tot;i++) solve(pri[i]); if(b1!=1)solve(b1); printf("%d\n",ans); } return 0; } |
OI 课件=>
蒟蒻请教黄学长 分解因数那个为什么solve b1?? 发现不solve就只有90分
可能最后还是一个质数。。。
那个暴力的代码有一个地方打错了。。。。。