被坑了好久(还是因为我太菜了)。。
说下我的思路历程,因为a1是x的约数,b1/b0也是x的约数,所以我找了a1和b1/b0的最小公倍数a,符合条件的x必定是a的倍数。
这个思路提交,时间超限73。
后来参考大佬写法,让i依次加一截至到i*i>b1,时间超限93.
最后发现因为用了longlong输入,改成int以后时间立马从两千四降到四百。
离谱离谱。。(以后都自己写read了)
参考代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cmath> #include<vector> #include<set> #include<sstream> #include<cstring> #include<utility> using namespace std; typedef long long ll; typedef long l; const int N=1<<10+1; int n,a1,a0,b1,b0; int gcd(int x,int y){ return y==0?x:gcd(y,x%y); } int main(){ cin>>n; while(n--){ scanf("%d%d%d%d",&a0,&a1,&b0,&b1); int cnt=0; for(int i=1;i*i<=b1;i++){ if(b1%i!=0)continue; if(gcd(a0,i)==a1&&b0*i==b1*gcd(b0,i)){ cnt++; } if((i*i)!=b1){ int x=b1/i; if(gcd(a0,x)==a1&&b0*x==b1*gcd(b0,x)){ cnt++; } } } cout<<cnt<<endl; } }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:517 |
校门外的树 (C语言代码)浏览:693 |
【求[X,Y]内被除3余1并且被除5余3的整数的和】 (C语言代码)浏览:673 |
DNA (C语言描述,蓝桥杯)浏览:1553 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:606 |
蚂蚁感冒 (C语言代码)浏览:1324 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:485 |
简单的a+b (C语言代码)浏览:544 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:554 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:1189 |