数论 最大公约数 P7847题解

Prean · 2021-08-23 18:18:38 · 题解

题意：给定 n ，求方程 \frac 1 a - \frac 1 b=\frac 1 n 的所有解，且解必须满足 \gcd(a,b,n)=1 。

以下内容搬运自官方题解：

转化一下：

根据 \gcd(a,b,n)=1 ，有：

接下来设 b=x \times \gcd(b,n),n=y \times \gcd(b,n) ，那么一定有 \gcd(x,y)=1 。

于是：

而 \gcd(xy,x+y)=1,\frac {xy} {x+y} \times \gcd(b,n) 是整数，所以有 (x+y)|\gcd(b,n) 。

于是 x+y=\gcd(b,n),b+n=\gcd(b,n) \times (x+y) = \gcd(b,n)^2 。

相当于求方程 x+n=\gcd(x,n) 。（这里的 x 在上面是 b ）

下面为了方便，设 \gcd(x,n)=d,c=dk 。

然后对于 d ，枚举可行的 k ，最后检查一下是否合法就行。

检查是否合法的瓶颈在于，计算 \gcd(x,c)=\gcd(d(d-k),c)=\gcd(d(d-k),dk)=d \times \gcd(d-k,k) 。

这里的 d-k 和 k 一定有一个数不大于 \sqrt n ，所以根据 \gcd(a,b)=\gcd(a \bmod b,b) ，可以直接预处理一个 \sqrt n \times \sqrt n 的表。

再往下推，发现实际上是判断 d \times \gcd(d-k,k)=d ，也就是判断 d 和 k 是否互质，所以打表可以使用一个 bool 类型的数组来降低常数。

到这里，复杂度已经变成 O(n\log n+T) 的了。在加强版中，这个做法只跑了 1s，并且卡掉了 O(n+T\sqrt n) 的暴力，还在原版跑到了300ms。

#include<cstdio>
#include<vector>
typedef unsigned uint;
typedef unsigned long long ull;
const uint M=2e6;
uint T,mx,n[100005],ans1[M+5];bool _check[1420][1420];
ull ans[M+5],ans2[M+5];
inline ull min(const ull&a,const ull&b){
    return a>b?b:a;
}
signed main(){
    register uint i,j,x;
    scanf("%u",&T);_check[0][1]=true;
    for(i=1;i<=1415;++i)_check[1][i]=true;
    for(i=2;i<=1415;++i){
        for(x=0,j=i;j<=1415;++j){
            _check[i][j]=_check[x][i];
            if(++x==i)x=0;
        }
    }
    for(i=1;i<=T;++i)scanf("%u",n+i),mx=n[i]>mx?n[i]:mx;
    for(i=1;i<=mx;++i)ans2[i]=0x7f7f7f7f7f7f7f7f;
    for(i=1;i<=mx;++i){
        for(j=1,x=i;j<=i&&x<=mx;++j,x+=i){
            if(_check[i%j][j])ans2[x]=min(ans2[x],1ull*i*(i-j)),++ans1[x];
        }
    }
    for(ans1[i=1]=0;i<=mx;++i)ans1[i]+=ans1[i-1];
    for(i=1;i<=T;++i)printf(n[i]==1?"0\n":"%u %llu\n",ans1[n[i]],ans2[n[i]]);
}