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

?

一行一個整數表示答案，保證不超過64位整數范圍。

?

對于20%的數據n<=1000；
對于40%的數據n<=100000；
對于60%的數據n<=10000000；
對于80%的數據n<=1000000000000；
對于100%的數據n<=100000000000000。

?

---

?

很明顯，20分的暴力是肯定有的，但是，正解怎么來呢？

得到正解需要證明兩個前置性質:

設d=gcd(a,b);

->a1=a/d?? b1=b/d;

第一個：

因為a1,b1互質

->?? gcd(a1,b1)==1

->?? gcd(a1+b1,a1)==1? gcd(a1+b1,b1)==1

->?? gcd(a1+b1,a1*b1)==1

第二個：

當ab是a+b的倍數時。

???? a+b|ab

->? d(a1+b1)|d^2*a1*b1

->? a1+b1|d*a1*b1

因為gcd(a1+b1,a1*b1)==1

->?? d=k(a1+b1);

?

現在我們在轉到題目上來：

???? a+b<=n

->? d(a1+b1)<=n

->? k(a1+b1)^2<=n

->? k<=n/(a1+b1)^2

?

我們枚舉(a1+b1),只有sqrt(n)的復雜度，因為k肯定是正整數。

假設我們現在枚舉到了(a1+b1)==x,

那么在n的范圍內的a+b有n/x^2個(k有這么多個)

而每個a+b有可以對應不同的ab，這里的ab數目正好是(a1+b1)的歐拉函數(相信可以理解的);

?

最終，我們的答案就是:

for(int i=1;i<=sqrt(n);i++)

{

　　ans+=phi[i]*n/i/i;

}

代碼：

∑n√i=1φ(i)?ni

?

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm>#define ll long long #define il inline #define db doubleusing namespace std;ll prime[10000045],cnt;ll phi[10000045];bool vis[10000045];il void init() {for(int i=2;i<=10000000;i++){if(!vis[i]){prime[++cnt]=i;phi[i]=i-1;}for(int j=1;j<=cnt;j++){if(prime[j]*i>10000000)break;vis[prime[j]*i]=1;if(i%prime[j]==0){phi[prime[j]*i]=phi[i]*prime[j];break;}elsephi[prime[j]*i]=phi[i]*(prime[j]-1);}} }int main() {init();//xian xing shai qiu phill n;cin>>n;int p=sqrt(n);ll ans=0;for(int i=1;i<=p;i++)ans+=phi[i]*n/i/i;//suan chu lai deprintf("%lld\n",ans);return 0; }

?

?

daia

轉載于:https://www.cnblogs.com/gshdyjz/p/7678533.html

總結

以上是生活随笔為你收集整理的神炎皇 数学的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。