神炎皇 题解【数学】【gcd】【欧拉函数】

点击量：220

    怎么才能想到可以这样推啊……数学题做少了orz。

目录

问题描述

神炎皇乌利亚很喜欢数对，他想找到神奇的数对。

对于一个整数对\((a,b)\)，若满足\(a+b\le n\)且\(a+b\)是\(ab\)的因子，则成为神奇的数对。请问这样的数对共有多少呢？

输入格式

一行一个整数\(n\)。

输出格式

一行一个整数表示答案， 保证不超过\(64\)位整数范围。

输入输出样例

uria.in	uria.out
21	11

数据范围与约定

对于\(20\%\)的数据\(n\le 1000\)；
对于\(40\%\)的数据\(n\le 100000\)；
对于\(60\%\)的数据\(n\le 10000000\)；
对于\(80\%\)的数据\(n\le 1000000000000\)；
对于\(100\%\)的数据\(n\le 100000000000000\)。

题解：

    这个题需要用\(\gcd\)来推，题目条件要求\((a+b)|ab\)，这一条件看上去非常不好用，于是考场上就打了\(O(n^2)\)的暴力，拿了\(20\)。

    若\((a+b)|ab\)，则\(\gcd(a+b,ab)=a+b\)。设\(d=\gcd(a,b)\)，\(a’=\frac ad,b’=\frac bd\)。

    题目条件变成了\((a’d+b’d)|a’b’d^2\)，左右同除以\(d\)，得\((a’+b’)|a’b’d\)。此时由于\(a’\perp b'(\gcd(a’,b’)=1)\)，所以\(\gcd(a’+b’,a’)=1\)，\(\gcd(a’+b’,b’)=1\)。

反证：

若\(\gcd(a’+b’,a’)\not=1\)，则令其为\(k\)，一定存在整数\(p,q\)使得\(a’+b’=kp,a’=kq\)，因此\(b’=k(q-p)\)，则\(\gcd(a’,b’)=k\)，与上文\(a’\perp b’\)矛盾。

    那么根据\((a’+b’)|a’b’d\)，且\((a’+b’)\perp a’,(a’+b’)\perp b’\)，则\((a’+b’)|d\)。由此得出令原式\((a+b)|ab\)成立的条件就是\((a’+b’)|d\)。

    而我们反观\((a’+b’)|d\)的意义，得出\(k(a’+b’)=d,k\in \bf{N^*}\)。

\(\because k\ge 1\)，

\(\therefore a’+b’\le d\)，又\(\because a+b\le n\)，

\(\therefore a’d+b’d\le n\Rightarrow (a’+b’)d\le n\)，移项得\(d\le \frac{n}{a’+b’}\)；

\(\because a’+b’\le d\)，

\(\therefore (a’+b’)\le \frac{n}{a’+b’},(a’+b’)^2\le n\)。

    至此，我们把一个问题转化到了\(\sqrt{n}\)的范围内。而数据范围正好是\(10^{14}\)，考虑继续做下去。

    因为原式成立的条件是\((a+b)|ab\Leftrightarrow (a’+b’)|d\)，所以我们只需要找出有多少组有序数对\((a’,b’,d)\)就可以了。

    若使\((a’+b’)|d\)成立，则\(d=k(a’+b’),k\in \bf{N^*}\)，由于\(k\)不同导致\(a,b\)不同，所以每组数对的贡献不一样。每组数对的贡献就是合法的\(k\)的个数，因此为\(\left\lfloor\frac{d}{a’+b’}\right\rfloor\)。又因为\(d\)可以是任意\(a’+b’\)的倍数，所以\(d\)的取值又有\(\left\lfloor\frac{n}{a’+b’}\right\rfloor\)种，合二为一，二元数对\((a’,b’)\)贡献了\(\left\lfloor\frac{n}{a’+b’}\right\rfloor\)种\(d\)，\(d=\left\lfloor\frac{n}{a’+b’}\right\rfloor\)，三元数对\((a’,b’,d)\)贡献了\(\left\lfloor\frac{d}{a’+b’}\right\rfloor\)种解，那么二元数对\((a’,b’)\)的贡献就是每个\(d\)的贡献，带入\(d\)得\((a’,b’)\)的贡献就是\(\left\lfloor\frac{n}{(a’+b’)^2}\right\rfloor\)。

    在最开始我们提到了\(\gcd(a’,b’)=1\)，也就是数对还需要满足的一个条件。因为这一条件不好控制\(a’\)和\(b’\)的大小，所以我们把数对换成\((a’,a’+b’)\)，此时依然满足\(\gcd(a’,a’+b’)=1\)，而且\(a'<a’+b’\le \sqrt{n}\)。那么我们直接枚举\(a’+b’\)的值\(i\)，\(\varphi(i)\)就是合法的\(a’\)个数，数对的答案仍然是\(\left\lfloor\frac{n}{(a’+b’)^2}\right\rfloor\)，因为此时枚举的是\(i=a’+b’\)，所以答案为\(\sum_{i=2}^{\sqrt{n}}\left\lfloor\frac{n}{i^2}\right\rfloor\cdot \varphi(i)\)。时间复杂度为\(O(\sqrt{n})\)。

Code：

#include<cmath>
#include<cstdio>
#include<cstring>
int phi[10001000];
int pri[1001000],cnt=0;
bool isnt[10001000];
void init(int n)//线性计算欧拉函数
{
    isnt[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(!isnt[i])
        {
            pri[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
        {
            isnt[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
}
int main()
{
    long long n;
    scanf("%lld",&n);
    int up=sqrt(n);
    init(up);
    long long ans=0;
    for(int i=2;i<=up;++i)
        ans+=n/i/i*phi[i];//统计答案
    printf("%lld\n",ans);
    return 0;
}