神炎皇解题报告

神炎皇

问题描述

神炎皇乌利亚很喜欢数对，他想找到神奇的数对。
对于一个整数对((a,b))，若满足 (a+ble n) 且 (a+b) 是 (ab) 的因子，则称为神奇的数对。请问这样的数对共有多少呢？

输入格式

一行一个整数 (n)。

输出格式

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

数据范围与约定

对于(20\%)的数据 (nle 1000)；

对于(40\%)的数据 (nle 100000)；

对于(60\%)的数据 (nle 10000000)；

对于(80\%)的数据 (nle 1000000000000)；

对于(100\%)的数据 (nle 100000000000000)。

说一下考试时候的打表历程吧（拿了(40pts)，如果让我交答案表了就有(60pts)了）

第一个表的枚举(a+b)，然后暴力找(a,b)

得到了一个没什么用的答案表

把数对打出来

研究一下发现每个(a+b)的贡献可以这么算,设(f(x))为(x=a+b)的贡献

则(f(x)=sum_{i=1}^x[x|i^2])

证明一下也不难，因为(gcd(i,x)=gcd(x-i.x))

发现这样没什么卵用，继续打表发现

后面的都是第一个的倍数，理解起来也非常简单，考虑每个数最小满足的数怎么搞。

发现就是唯一分解以后，指数除(2)向上取整，拿原数除最小数即为个数(-1)（因为自己不算），则又有

(x=prod p_i^{c_i})，(f(x)=prod p_i^{lfloorfrac{c_i}{2} floor}-1)

令(g(x)=prod p_i^{lfloorfrac{c_i}{2} floor})

发现(g(x))是积性函数，然而窝并没想到(O(n))的筛法，只好只拿了(40pts)

正解：

设有一对满足条件的数对((a,b))

设(d=gcd(a,b),a'=frac{a}{d},b'=frac{b}{d})

则要满足条件((a'+b')d|a'b'd^2)

即((a'+b')|a'b'd)

因为((a',b')=1),所以((a'+b',a')=(a'+b',b')=1)，所以((a'+b',a'b')=1)

则条件为((a'+b')|d)

设(i=a'+b')，(d=ki)，那么有(id=i^2kle n)

发现枚举(i)只需要到(sqrt n)就可以了，于是枚举(i)

对于一个(i)，(k)的取值个数为(lfloorfrac{n}{i^2} floor)

考虑(i)内部的情况，发现是(varphi(i))，原因很简单，也是因为(gcd(i,x)=gcd(i,i-x))，考虑一下成对出现就可以了。

那么答案就为(sum_{i=1}^{sqrt n}varphi(i)lfloorfrac{n}{i^2} floor)

总结：

数据范围根号提示
想办法使用(varphi ,mu)什么的
胡乱更换枚举项试试（这是很多题的核心了，谁枚举的少好算，我就找谁）
不要忘记打个表

Code:

#include <cstdio>
#define ll long long
const int N=1e7;
int pri[N+10],phi[N+10],ispri[N+10],cnt;
ll ans,n;
void init()
{
    for(int i=2;i<=N;i++)
    {
        if(!ispri[i])
        {
            pri[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&pri[j]*i<=N;j++)
        {
            ispri[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            else
                phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
}
int main()
{
    init();
    scanf("%lld",&n);
    for(ll i=1;i*i<=n;i++)
        ans=ans+phi[i]*(n/(i*i));
    printf("%lld
",ans);
    return 0;
}

2018.11.1

神炎皇 解题报告

神炎皇

问题描述

输入格式

输出格式

数据范围与约定

神炎皇解题报告