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

本文主要是介绍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,tmp,mod);n>>=1;}return ret;
}bool check(long long a,long long n,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,x,t))return false;}return true;
}int main()
{ll n;while(scanf("%lld",&n)!=EOF){if(n == 1 || n == 2){printf("No\n");continue;}if(Miller_Rabin(n) || n == 4)printf("Yes\n");else printf("No\n");}
}

这篇关于nyist 468 Fibonacci数列（六）(Miller-Rabin算法 大数素性测试)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---