題意

交表 由于f(k?x,k?y) 可以由f(x,y)遞推出來 讓我們求 在x，y都不大于n的情況下
計算最少需要計算多少不同的項
n<=50000

分析

那么也就是說兩個數由共因子的不必計算 只計算兩個數沒有共因子的 那么也就是說 每個數我們只需要找到與他互質的個數就可以了 歐拉函數線性篩
求歐拉函數復雜度O(n*logn*logn)

code

#include<bits/stdc++.h> using namespace std; const int maxn = 50010; int phi[maxn]; void init(){phi[1]=1;for(int i=2;i<maxn;i++){if(!phi[i])for(int j=i;j<maxn;j+=i){if(!phi[j])phi[j]=j;phi[j] = phi[j]/i*(i-1);}} } int main(){int n;init();while(scanf("%d",&n),n){int ans=1;for(int i=n;i>1;i--){//（1，1）就算一次就夠了ans+=phi[i]<<1;//符合條件的*2 (x,y)+（y,x）}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的UVa-10820 Send a Table 欧拉函数的全部內容，希望文章能夠幫你解決所遇到的問題。

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