90tps,测试点3WA,求助

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

YaemikooO3 @ 2024-05-03 11:04:43

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll res,p,q;
ll gcd (ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll x,y;cin>>x>>y;
    ll t=x*y;
    p=x;
    while(p*p <=t){
        if(p*p==t) res--;//恰为完全平方数 
        q=t/p;
        if(p*q==t)//确定了p和q确实是正整数 
            if(gcd(q,p)==x) res+=2;
        p+=x;//保证x是他的因数
    }
    cout<<res;
    return 0;
}

这可真是怪事,只有我是这样吗,我看大伙代码都不判q是不是正整数来着.....


by BJ_BSGF_Lyc @ 2024-05-12 10:37:52

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

你这个已经有ios::大法了,没必要手写GCD。

实际上这道题可以直接这么写:

for(int i=n;i<=m;i++){
    int j=n*m/i; 
    if(__gcd(i,j)==n&&i*j/__gcd(i,j)==m) s++;
}

这里可以用一个库函数__gcd,这题就可以直接秒杀。


|