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

作者: wjyyy 分类: gcd/lcm,数学,欧拉函数,解题报告 发布时间: 2018-11-01 18:31

点击量:62

 

    怎么才能想到可以这样推啊……数学题做少了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;
}

说点什么

avatar
  Subscribe  
提醒
/* */