題目

神炎皇烏利亞很喜歡數(shù)對(duì)，他想找到神奇的數(shù)對(duì)。
對(duì)于一個(gè)整數(shù)對(duì)(a,b)，若滿足a+b<=n且a+b是ab的因子，則成為神奇的數(shù)對(duì)。請(qǐng)問這樣的數(shù)對(duì)共有多少呢？

分析

設(shè)\(gcd(a,b)=d,a'd=a,b'd=b\)
那么\(a'+b'|a'b'd\)
因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(gcd(a',b')=1\)
所以\(a'+b'|d\)。
又因?yàn)?span id="ze8trgl8bvbq" class="math inline">\((a'+b')d<=n\)
則\(a'+b'=\sqrt n\)
枚舉\(a'+b'=i\)
\(d就有\(zhòng)dfrac{n}{i^2}種情況\)
因?yàn)?span id="ze8trgl8bvbq" class="math inline">\(gcd(a',b')=gcd(a'+b',a')\)
所以\(a'和b'又有\(zhòng)varphi(i)種\)
線篩求\(\varphi()\)，時(shí)間復(fù)雜度\(O(\sqrt n)\)

#include <cmath> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <queue> const int maxlongint=2147483647; const int mo=1000000007; const int N=10000005; using namespace std; long long ans; long long n,qn,r,phi[N],p[N]; bool bz[N]; long long gcd(long long x,long long y) {for(;y;){r=x%y;x=y;y=r;}return x; } int main() {scanf("%lld",&n);qn=sqrt(n); phi[1]=1;memset(bz,true,sizeof(bz));for(long long i=2;i<=qn;i++){if(bz[i]) { bz[i]=false; p[++p[0]]=i; phi[i]=i-1; } for(long long j=1;j<=p[0] && i*p[j]<=qn;j++) {bz[i*p[j]]=false;if(i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);else {phi[i*p[j]]=phi[i]*p[j]; break;} }ans+=(long long)phi[i]*(long long)(n/i/i); } printf("%lld",ans); }

轉(zhuǎn)載于:https://www.cnblogs.com/chen1352/p/9066604.html

總結(jié)

以上是生活随笔為你收集整理的【NOIP2017提高组模拟12.10】神炎皇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。