BZOJ4802:欧拉函数(Pollard-Rho,欧拉函数)

Description

已知N,求phi(N)

Input

正整数N。N<=10^18

Output

输出phi(N)

Sample Input

8

Sample Output

4

Solution

一开始读错题了……以为是求约束个数和……

读对题之后然后发现我不会就问旁边的宽嫂……网址:yii666.com

宽嫂:这不是欧拉函数的定义式么?我初中就会了啊。

我:aaarticlea/jpeg;base64,/9j/4AAQSkZJRgABAQEAAQABAAD/2wBDAAYEBQYFBAYGBQYHBwYIChAKCgkJChQODwwQFxQYGBcUFhYaHSUfGhsjHBYWICwgIyYnKSopGR8tMC0oMCUoKSj/2wBDAQcHBwoIChMKChMoGhYaKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCj/wAARCAA1AEYDASIAAhEBAxEB/8QAHwAAAQUBAQEBAQEAAAAAAAAAAAECAwQFBgcICQoL/8QAtRAAAgEDAwIEAwUFBAQAAAF9AQIDAAQRBRIhMUEGE1FhByJxFDKBkaEII0KxwRVS0fAkM2JyggkKFhcYGRolJicoKSo0NTY3ODk6Q0RFRkdISUpTVFVWV1hZWmNkZWZnaGlqc3R1dnd4eXqDhIWGh4iJipKTlJWWl5iZmqKjpKWmp6ipqrKztLW2t7i5usLDxMXGx8jJytLT1NXW19jZ2uHi4+Tl5ufo6erx8vP09fb3+Pn6/8QAHwEAAwEBAQEBAQEBAQAAAAAAAAECAwQFBgcICQoL/8QAtREAAgECBAQDBAcFBAQAAQJ3AAECAxEEBSExBhJBUQdhcRMiMoEIFEKRobHBCSMzUvAVYnLRChYkNOEl8RcYGRomJygpKjU2Nzg5OkNERUZHSElKU1RVVldYWVpjZGVmZ2hpanN0dXZ3eHl6goOEhYaHiImKkpOUlZaXmJmaoqOkpaanqKmqsrO0tba3uLm6wsPExcbHyMnK0tPU1dbX2Nna4uPk5ebn6Onq8vP09fb3+Pn6/9oADAMBAAIRAxEAPwD6przvxJ8QfDWgXn2PUtYiivfK/wBRFFLPKv8A36ra8XT3Gn+HNYu9O8r+0IIJWg82Xy4vN8qvFfhPca9q1npq+GNMn0axNx9qvNYvJYpZdT/56/8ALKgD0h/il4c/1WkS3usXEsXm+VpNnLcS1F/ws6KL97e+EPF0EX/PWXTK6DU/GHhzR7z+z72+iguIv+WFQw/EHwxI3lS6vaxXH/PCWX97QAaT488Oalo51C31izitvN8rzblvs/73/trXTWN5BfQeZZT288X96KXza5rxZ4b0/X7X7ZFpmkXmpeV+4l1Gz+1RV454aidPGmjyeBtG1LTJ4J4l1zyoJbKxli/65S/8taAPdPFGuw6FbWhLI93e3SWVnFLL5SSzvu2qz/w/db/2VWfajU/C/if+2tR1rR7uGO31vR5IkvreGVpYk81d8TJIyruBXP8ACuGVuMbWbe1DTLLUDbm/tILk206XEPnxK/lyrnbIv91v9qvP/gRYyJ4NTWdUlgvPEOrzST6jfRXUdz9pZZWWP95EzLtRNi7V+VeenNAHqdFFFAHkvxQxqeteEvCHmxRWWsXkst4P+ekVvF5vlf8AoqvSbaCKC38iKL91XAfEfw3qOpQaZfaNdIut6PP9os/NH7uX91+9il/661n+HvixZ3Eps/EGlappl7HP9nf9x9og8z/plLFQB0Nx4W8Ot4je+lX/AEiKWL5P+WSy/wDLKsxfA3g7xHf/ANr2sXmyxf8APvJ5UUtavjnR9cv4N2iavf24T/l1gji/e/8AbWWk+H+ha9o/2hdd1X+0bf8A5ZebF+9WgDsoYoooooovuRV514mg/wCEb+IGl+IomiistTf+y9Qj8v70v/LCX/2l/wBta9Lrz7406dJqHw+1uODi4gg+2wS/3ZYv3v8A7SoA9HrL0zTrPS7GKy0u0t7O1jP7uC2iWKJT977q1U8N6jFqejWV9F/qryCK4/7+1v0AFFFFABXnPwVlin8F/bP+Wt5eXlxL/wCBUtejV4B4O1jVNG+HOmNoujy37Qajf289vH/rY/3svlf+RfKoA95pnlVzngjTtQ0/wvpkGv3kt5qcUX7+eWT/AJa11lAFN5YoIjI8nyR1jN5Gu6Nd+QyT22oQfupY/wDlrFLFXIfEjwtr2p3sM/h28t4vPs5dKvPP/wCWUEv/AC1i/wCmtdhYwWeheH4oIv3Vlp0Hlf8AbKKKgDn/AIIXn2z4ZeF/N/1sVn5X/fr91XoleXfAu18j4W+GfN/1skXm/wDf2Xza9RoAKKKKACua0/Q7DSfNhsYFjSeW4uHx/ebrRRQB0NSUUUAFVTAs1vtl+YUUUAQwQxwiKGJdsXlfdrQoooAKKKKAP//Z" alt="" />

然后去百度了一发,发现一个数的欧拉函数就是文章地址https://www.yii666.com/article/756192.html网址:yii666.com<文章来源地址:https://www.yii666.com/article/756192.html

$\prod (p_i-1)*p_i^{k_i-1}$,其中$p_i$是这个数的质因子,$k_i$是这个质因子的次数……

然后套板子就行了。

发现我之前抄了个假的快速乘然后还花了我一会儿改代码+改博客……QAQ文章来源地址https://www.yii666.com/article/756192.html

Code

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#define LL long long
using namespace std; LL n,ans=,Num[],cnt;
LL prime[]={,,,,,,,,,,};
map<LL,LL>Keg; LL Mul(LL a,LL b,LL MOD)
{
LL tmp=a*b-(LL)((long double)a*b/MOD+0.1)*MOD;
return tmp<?tmp+MOD:tmp;
} LL Qpow(LL a,LL b,LL MOD)
{
LL ans=;
while (b)
{
if (b&) ans=Mul(ans,a,MOD);
a=Mul(a,a,MOD); b>>=;
}
return ans;
} LL gcd(LL a,LL b) {return b==?a:gcd(b,a%b);} bool Miller_Rabin(LL n)
{
if (n==) return ;
if (n< || n%==) return ;
LL m=n-,l=;
while (m%==) m>>=, l++;
for (int i=; i<; ++i)
{
LL p=prime[i],w=Qpow(p,m,n);
if (w==n- || w== || p==n) continue;
for (int j=; j<=l; ++j)
{
LL u=Mul(w,w,n);
if (u== && w!=n- && w!=) return ;
w=u;
}
if (w!=) return ;
}
return ;
} LL Pollard_Rho(LL n,LL c)
{
LL x=(rand()+)%n,y=x,p=,k=;
for (LL i=; p==; ++i)
{
x=(Mul(x,x,n)+c)%n;
p=x>y?x-y:y-x;
p=gcd(p,n);
if (i==k) y=x, k=k+k;
}
return p;
} void Solve(LL n)
{
if (n==) return;
if (Miller_Rabin(n))
{
if (!Keg[n]) Num[++cnt]=n;
++Keg[n]; return;
}
LL t=n;
while (t==n) t=Pollard_Rho(n,rand()%(n-)+);
Solve(t); Solve(n/t);
} int main()
{
scanf("%lld",&n);
Solve(n);
for (int i=; i<=cnt; ++i)
ans=ans*(Num[i]-)*Qpow(Num[i],Keg[Num[i]]-,2e18);
printf("%lld\n",ans);
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

BZOJ4802:欧拉函数(Pollard-Rho,欧拉函数)-相关文章

  1. c语言总练习题

  2. BZOJ4805: 欧拉函数求和(杜教筛)

  3. BZOJ4802 欧拉函数 数论

  4. 【刷题】BZOJ 4805 欧拉函数求和

  5. BZOJ4802:欧拉函数(Pollard-Rho,欧拉函数)

  6. BZOJ 4802 欧拉函数

  7. bzo4802 欧拉函数 miller_rabin pollard_rho

  8. C++刷题——2830: 递归求1*1+2*2+3*3+……+n*n

      心得体会:这是一个简单递归函数,假设遇到复杂的递归函数。在写之前能够先找找规律,写成递归的形式。就比較好些了。继续努力。

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png