当前位置: 代码迷 >> 综合 >> hdu6440--Dream(小费马定理 构造)
  详细解决方案

hdu6440--Dream(小费马定理 构造)

热度:51   发布时间:2023-12-26 10:13:14.0

这道题刚开始没有好好读题,就只是一味Output里给的就是对应每个位置的数值的表达式。然后,,打表,,然后发现了规律。写写写,然后交了,然后WA了。。

这道题是一道构造题吧。

保证p是素数,要求构造一个加法和乘法运算,使。
因为给定的p是素数,根据费马小定理得

又由题上说,

因此,
所以,
所以在模p下, 恒成立,且加法运算与乘法运算封闭。(如果能够做到做运算的结果还在这个集合中,就说这个集合对乘法运算封闭。)

【代码】

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
typedef long long LL;
int main()
{int T,p;scanf("%d",&T);while(T--){scanf("%d",&p);for(int i=0;i<p;i++)for(int j=0;j<p;j++)printf("%d%c",(i+j)%p,j==p-1?'\n':' ');for(int i=0;i<p;i++)for(int j=0;j<p;j++)printf("%d%c",(i*j%p),j==p-1?'\n':' ');}return 0;}