被坑了好久(还是因为我太菜了)。。
说下我的思路历程,因为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.3 (C语言代码)浏览:718 |
WU-C语言程序设计教程(第三版)课后习题12.1 (C++代码)浏览:941 |
1642题解浏览:716 |
字符逆序 (C语言代码)浏览:460 |
简单的a+b (C语言代码)浏览:582 |
C二级辅导-统计字符 (C语言代码)浏览:481 |
企业奖金发放 (C语言代码)浏览:2325 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:649 |
求圆的面积 (C++代码)浮点数有误差!!!浏览:675 |
用筛法求之N内的素数。 (C语言代码) 详解………………浏览:1024 |