题解报告：hdu 6440 Dream（费马小定理+构造）

解题思路：给定素数p，定义p内封闭的加法和乘法运算（运算封闭的定义：若从某个非空数集中任选两个元素（同一元素可重复选出），选出的这两个元素通过某种（或几种）运算后的得数仍是该数集中的元素，那么，就说该集合对于这种（或几种）运算是封闭的。），使得等式$(m+n)^p = m^p + n^p(0 \leq m,n<p) $恒成立。

由费马小定理可得$(m+n)^p\equiv(m+n)(mod\;p)$,则$m^p + n^p \equiv(m+n)(mod\;p)$。

∴在模p的意义下，$ (m+n)^p = m^p + n^p(0 \leq m,n<p)$恒成立，且加法运算与乘法运算封闭。

因为在p是素数的情况下，对任意的整数x都有$x^p\equiv x(mod\;p)$，即有$ m^p\equiv m(mod\;p),n^p\equiv n(mod\;p)$，所以乘法运算满足$m^p \cdot n^p \equiv m\cdot n(mod\;p)$。

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 int t,p;

 int main(){

     while(cin>>t){

         while(t--){

             cin>>p;

             for(int i=;i<p;++i)

                 for(int j=;j<p;++j)

                     printf("%d%c",(i+j)%p,j==p-?'\n':' ');

             for(int i=;i<p;++i)

                 for(int j=;j<p;++j)

                     printf("%d%c",i*j%p,j==p-?'\n':' ');

         }

     }

     return ;

 }

巴特西

题解报告：hdu 6440 Dream（费马小定理+构造）

最新文章

热门文章