大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
（1）费马小定理结论：结论是若存在整数 a , p 且gcd(a,p)=1,即二者互为质数，则有a(p-1)≡ 1(mod p)。(这里的 ≡ 指的是恒等于，a(p-1)≡ 1(mod p)是指a的p-1次幂取模与1取模恒等)，再进一步就是ap≡a(mod p)。
继续学习：中国剩余定理、拓展欧几里得(exgcd)、求除法逆元、费马小定理
（2）费马大定理结论：又被称为“费马最后的定理”，常见的表述为当整数n>2时，关于xn + yn = zn 的方程没有正整数解。
当n=0时，实数范围只有x=0,y=0,z=0时才是解,当n=1时，就是一个加减法，当n=2时，就类似于勾股定理。
构造勾股数的四种表现形式：
（1）2n+1、2n2+2n、2n2+2n+1（n为正整数）是一组勾股数。
（2）2(n+1)、n2+2n、n2+2n+2（n为正整数）是一组勾股数。
（3）m2-n2、2mn、m2+n2（m、n表示两个不同的正整数且m>n）是一组勾股数。
（4）如果a、b、c是一组勾股数那么na、nb、nc（n为正整数）也是一组勾股数。
应用费马小定理：
题目链接：杭电oj 6440
http://acm.hdu.edu.cn/showproblem.php?pid=6440
题意：
给一个质数p，重新定义 + 和 * 使得（m+n)p= mp + np;(其中 m , n 指的是小于p的非负整数 ），使得对于任意的n,m属于[0,p-1]，满足式子，最后，输出两个n*n的矩阵表示加法和乘法的结果，对于1到p行，你将要输出第i行与第j列的数相加的结果；对于第p+1行到2p行，你将要输出第i行与第j列相乘的结果。
题解：个人理解就是让你选一个操作让(m+n)p=mp+np(0<=m,n<p)。成立，最后输出操作之后的值。因为给定的是素数，根据费马小定理得=(m+n)p-1≡1(mod p),因此，mp+np≡m+n(mod p)。所以在模p的意义下，(m+n)p=mp+np(0<=m,n<p)恒成立，且加法运算与乘法运算封闭。
下面附AC代码：
#include<iostream>
using namespace std;
int t,p;
int main()
{
cin>>t;
while(t--)
{
cin>>p;
for(int i=0;i<p;i++){
for(int j=0;j<p-1;j++){
printf("%d ",(i+j)%p);
}
printf("%d\n",(i+p-1)%p);
}
for(int i=0;i<p;i++){
for(int j=0;j<p-1;j++){
printf("%d ",(i*j)%p);
}
printf("%d\n",(i*(p-1))%p);
}
}
return 0;
}
应用费马大定理：
题目链接：杭电oj 6441
https://acm.dingbacode.com/showproblem.php?pid=6441
题意：
构造an+bn=cn，a和n给出，求b和c，所以就成了一道构造题。
题解：
由费马大定理可得当n=0（因为题目中a>=3）或者n>2时输出-1 -1
当n=1时，构造一个加减法就可以了。当n=2时，用奇偶构造法求出勾股定理中另外两个数。
下面附AC代码：
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,a,t;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>a;
if(n>2||n==0)
printf("-1 -1\n");
else{
if(n==1){
printf("1 %d\n",a-1);
}
else{
if(a%2==0){
ll ans=a/2-1;
printf("%d %d\n",ans*ans+ans*2,ans*ans+ans*2+2);
}
else{
ll ans=(a-1)/2;
printf("%d %d\n",2*(ans*ans+ans),2*(ans*ans+ans)+1);
}
}
}
}
return 0;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/209528.html原文链接：https://javaforall.net
