 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:问一下，怎样快速求欧拉函数的值？In Reply To:问一下，怎样快速求欧拉函数的值？ Posted by:JiangLY at 2005-07-16 21:38:40 这道题不能直接求欧拉函数……因为你要算到10^9的欧拉函数 可以证明F(N) = ∑gcd(i, N) 1<=i<=N是积性函数： F(N) = ∑gcd(i, N) = ∑(d*phi(N/d)) d|N（这里枚举d，计算有多少个i满足gcd(i, N)==d） 由于f(d)=d和欧拉函数都是积性函数，所以F也是积性函数 然后推一个求F的公式，把输入的N分解质因数 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
