HDU-6440-费马小定理

时间:2022-05-03 12:57:32

亏我前几天还学数论呢。。。没有深入研究费马小定理这个东西。。。做事情一定要静下心来啊。。。

题目要求满足(m+n)^p=m^p+n^p,要你定义一个封闭的新的加法和乘法运算

我们知道费马小定理中有两种表示法

费马小定理:若p是素数且a是整数则a^p≡a(mod p),特别的若a不能被p整除,则a^(p-1)≡1(mod p).

这道题就可以这么解决

首先(m+n)^p=m^p+n^p都在%p的运算下进行,那么等式可以写为m+n=m+n(mod p)恒成立

那么我们就知道这个式子定义的新运算是在%p下进行的

我们把新的加法和乘法运算也变成在%p下进行的运算即可

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main(){
int t;
int p;
int ans1,ans2;
scanf("%d",&t);
while(t--){
scanf("%d",&p);
for (long long i=;i<=p;i++){
for (long long j=;j<=p;j++){
if(j!=p)printf("%lld ",(i-+j-)%p);
else printf("%lld\n",(i-+j-)%p);
}
}
for (long long i=;i<=p;i++){
for (long long j=;j<=p;j++){
if (j!=p)printf("%lld ",(j-)*(i-)%p);
else printf("%lld\n",(j-)*(i-)%p);
}
}
}
return ;
}