被坑了好久(还是因为我太菜了)。。
说下我的思路历程,因为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语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:812 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:868 |
c primer plus 第十二章 12.1小节浏览:377 |
wu-淘淘的名单 (C++代码)浏览:1339 |
【金明的预算方案】 (C++代码)浏览:843 |
2004年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:1341 |
用筛法求之N内的素数。 (C语言代码)浏览:806 |
C语言训练-自由落体问题 (C语言代码)浏览:615 |
Cylinder (C语言描述,蓝桥杯)浏览:1247 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:373 |