啊居然要特判,卡了好久QAQ
(好像Windows下的rand和Linux下的不一样?
QwQ一些东西参考了喵铃的这篇blog:http://www.cnblogs.com/meowww/p/6400841.html (业界良心)
题意:输入$n$,求$phi(n)$,$n \leq 10^{18}$
随便抽的题,刚好学习一下相关的算法。
很明显朴素的根号算法时间复杂度补滋兹,线性筛更不用想了,不过这题只需要单个欧拉函数值,还是直接考虑$phi(n)=n*\prod_{i=1}^k(1-\frac{1}{p_i})$这种求法吧,根号算法的瓶颈在于没办法快速确定有哪些约数,如果我们能快速的对$n$进行质因数分解就好了。
前置技能(pre-skill)
费马小定理
Miller-Rabin素性测试
Pollard-Rho大整数分解算法(zheng ti)
好了现在终于可以回到最开始的那个问题了,我们需要快速地对一个数进行质因数分解。
我们假装找到了一个因子
好了现在回到原来的题目,用Pollard-Rho算法分解出$n$的所有因子排个序就好辣。
注意:特判1 特判1 特判1
细节都在里面啦,我写的好像比较挫在bzoj上跑了一百多ms…
T_T搞不懂那些10ms内的怎么写的
#include
#include
#include
#include
#include
using namespace std;
typedef long long lint;
inline lint mul(lint a,lint b,lint p)
{
lint res=0;a%=p;b%=p;
for(;b;b>>=1,a=(a<<1)%p)if(b&1)res=(res+a)%p;
return res;
}
inline lint pow_mod(lint a,lint b,lint p)
{
lint res=1;a%=p;
for(;b;b>>=1,a=mul(a,a,p))if(b&1)res=mul(res,a,p);
return res;
}
inline lint gcd(lint a,lint b)
{
return !b?a:gcd(b,a%b);
}
inline lint get(lint x)
{
return rand()%x;
//return mul(mul(rand(),rand(),x),mul(rand(),rand(),x),x);
}
inline lint range(lint a,lint b)
{
return a+get(b-a+1);
}
inline bool check(lint x)
{
lint temp[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
for(register int i=0;i<15;i++)
{
if(x==temp[i])return 1;
if(x%temp[i]==0)return 0;
}
lint s,a,k=0,t=x-1;
while(!(t&1))
{
t>>=1;
k++;
}
for(register lint i=1;i<=20;i++)
{
a=range(2,x-1);
s=pow_mod(a,t,x);
if(s==1)return 1;
for(register lint j=0;j<=k-1;j++)
{
s=mul(s,s,x);
if(s==x-1)return 1;
}
}
return 0;
}
lint q[115],tot;
#define f(p) ((mul(p,p,x)+c)%x)
inline void solve(lint x)
{
if(check(x))
{
q[++tot]=x;return;
}
while(1)
{
lint a,b,c;
a=b=range(0,x-1);c=range(0,x-1);b=f(b);
while(a!=b)
{
lint temp=a-b;
temp=gcd(abs(temp),x);
if(1<temp&&temp<x)
{
solve(temp);solve(x/temp);
return;
}
a=f(a);b=f(f(b));
}
}
}
int main()
{
srand(19260817);
lint n,res;scanf("%lld",&n);
if(n==1)
{
printf("1");
return 0;
}
solve(n);sort(q+1,q+tot+1);
res=n;
for(register int i=1;i<=tot;i++)if(q[i]!=q[i-1])res=(res/q[i])*(q[i]-1);
printf("%lld",res);
return 0;
}
后记
到此为止算是啃完了meow那篇blog了,感觉受益匪浅。
其实暑假有学过这个算法但是当时还是不太清楚加上几个月没写基本上忘得差不多了,今天重新回来学了一遍应该算捡起来了。
在做这道题的时候顺便去查了些相关的东西,之前因为没有特判掉1所以一直挂掉加上今天下午去打了场比赛就这样基本花了一整天(虽然我中间还去打了几把game)
(听说我错别字特别多?)
手机扫一扫
移动阅读更方便
你可能感兴趣的文章