欧拉函数
在数论中,对正整数$n$,欧拉函数$\phi(n)$是小于或等于$n$的正整数中与$n$互质的数的数目。
求单个数的欧拉函数值时间复杂度可以为$Olog_2n$,代码如下:
1 2 3 4 5 6 7 8 9 10 11
| LL euler(LL n) { LL ans=n; for(int i=2;i*i<=n;i++){ if(n%i==0){ ans-=ans/i; while(n%i==0) n/=i; } } if(n>1) ans-=ans/n; return ans; }
|
素数n
的欧拉函数值是n-1
下面是一个用到上述函数的题目
---
1003 - 不是签到题XD
小明是一个贪心的孩子,他天天想着怎么让自己省钱。有一天他去商店买物品,然而他不是普通人,他有一个马基雅把库内的能力,可以只花掉商品价格与他今日幸运数字x的最大公约数的钱就能买走这个商品。那么问题来了,如果他要买价值从1到 x 元的 x 个商品,一共要花掉多少钱。
输入
输入包含一个整数,代表小明今日的幸运数字 x 。
输出
请输出小明的花费
样例
样例1的输入:
样例1的输出:
样例2的输入:
样例2的输出:
样例3的输入:
样例3的输出:
提示
$1\leq x \leq 10^{11}$
题解如下
本题化简公式如下:
$$
\sum_{i=1}^ngcd(i,x)=\sum_{k|x}k\phi(\frac{x}{k})
$$
还有一些小细节,可以在$O(\sqrt{n}\log_2n)$时间复杂度内求解。
代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #include<iostream> #include<map> #include<vector> #include<map> #include<set> #include<list> #include<climits> #include<algorithm> #include<cmath> #include<climits> #include<queue> #include<cstdio> #include<cstring> #include<stack> #include<iomanip> using namespace std; #define LL long long LL euler(LL n) { LL ans=n; for(int i=2;i*i<=n;i++){ if(n%i==0){ ans-=ans/i; while(n%i==0) n/=i; } } if(n>1) ans-=ans/n; return ans; } int main(){ ios::sync_with_stdio(0),cin.tie(0); LL n; while(cin>>n){ LL ans=0; for(int i=1;i<=sqrt(n);i++){ if(n%i==0) { ans+=euler(n/i)*i; if(n!=1) ans+=euler(i)*(n/i); } } cout<<ans<<endl; } return 0; }
|