nyist 468 Fibonacci数列（六）(Miller-Rabin算法 大数素性测试)

Fibonacci数列（六）

描述

大家都知道都知道素数的定义：大于1且只有1和其本身外没有其它因子的正整数。对应的我们可以这样定义"Fibonacci素数"：在Fibonacci数列中大于1且与小于它的Fibonacci数都互质的数。判断Fibonacci数列的第n项是否为"Fibonacci素数"。其中F ₁=F ₂=1,F _n=F _n-1+F _n-2 ?(n>2)。

输入

多组测试数据，不超过100组。

每行有一个整数n（0<n<10^18)。

输出

如果Fn为" Fibonacci素数"输出Yes，否则输出No，每个结果占一行。

样例输入

2

3

4

样例输出

No

Yes

Yes

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=468

题目分析：根据定理gcd(Fib[i],Fib[j]) = Fib[gcd(i,j)]可知只要n为素数，则Fib[n]是Fibonacci素数，注意4是一个特例，直接贴kuangbin巨巨的板子了

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const S = 20;   //随机算法判定次数，S越大，判错概率越小

long long mult_mod(long long a,long long b,long long c)
{
    a%=c;
    b%=c;
    long long ret=0;
    while(b)
    {
        if(b&1){ret+=a;ret%=c;}
        a<<=1;
        if(a>=c)a%=c;
        b>>=1;
    }
    return ret;
}

long long pow_mod(long long x,long long n,long long mod)
{
    if(n==1)return x%mod;
    x%=mod;
    long long tmp=x;
    long long ret=1;
    while(n)
    {
        if(n&1) ret=mult_mod(ret,tmp,mod);
        tmp=mult_mod(tmp,mod);
        n>>=1;
    }
    return ret;
}

bool check(long long a,long long x,long long t)
{
    long long ret=pow_mod(a,x,n);
    long long last=ret;
    for(int i=1;i<=t;i++)
    {
        ret=mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true;
        last=ret;
    }
    if(ret!=1) return true;
    return false;
}

bool Miller_Rabin(long long n)
{
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0) return false;
    long long x=n-1;
    long long t=0;
    while((x&1)==0){x>>=1;t++;}
    for(int i=0;i<S;i++)
    {
        long long a=rand()%(n-1)+1;
        if(check(a,n,t))
            return false;
    }
    return true;
}

int main()
{
    ll n;
    while(scanf("%lld",&n)!=EOF)
    {
        if(n == 1 || n == 2)
        {
            printf("Non");
            continue;
        }
        if(Miller_Rabin(n) || n == 4)
            printf("Yesn");
        else 
            printf("Non");
    }
}