一，判断题
5，×
10，√
15，×
20，√
25，√
30，×
35，×
二，单选题
5.D
10.D
15.B
27.B
四，综合题
a1≡b1 (mod m),a2≡b2 (mod m)
a1+a2≡b1+b2 (mod m)
∴a1+a2+...+ak≡b1+b2+...+bk (mod m)
a1≡b1 (mod m),a2≡b2 (mod m)
a1*a2≡b1*b2 (mod m)
∴a1*a2*...*ak≡b1*b2*...*bk (mod m)
（1）2^32 (mod47)
2^32=2^32
2^1≡2 (mod47)
2^2≡4 (mod47)
2^4≡16 (mod47)
2^8≡16^2≡21 (mod47)
2^16≡21^2≡18 (mod47)
2^32≡18^2≡42 (mod47)
∴2^32≡42 (mod47)
（2）2^47（mod47）
2^46≡1（mod 47）
2^47≡2^46*2≡1*2(mod 47)
2^47=2^32*2^8*2^4*2^2*2
2^32=2^32
2^1≡2 (mod47)
2^2≡4 (mod47)
2^4≡16 (mod47)
2^8≡16^2≡21 (mod47)
2^16≡21^2≡18 (mod47)
2^32≡18^2≡42 (mod47)
2^47≡42*21*16*4*2≡2（mod47）
∴2^47≡2（mod47）
（3）2^200（mod47）
∵2^46≡1 （mod 47）
200=46*4+16
2^200=2^(46*4)*2^16
2^200≡1^4*2^16（mod47）
2^16≡18（mod47）
（1）1843581
1+8+4+3+5+8+1=30
3|30，9不整除30
∴3整除1843581
（2）184234081
1+8+4+2+3+4+0+8+1=31
3和9都不整除31
∴3和9都不整除184234081
（3）8937752744
8+9+3+7+7+5+2+7+4+4=56
3|56,9|56
∴3和9都不能整除8937752744
（4）4153768912246
4+1+5+3+7+6+8+9+1+2+2+4+6=58
3|58,9|58
∴3和9都不能整除4153768912246
编程题
1.编程输出n的Euler函数值φ(n)
image.png
#include<iostream>
#include<cmath>
using namespace std;
int euler(int n)
{
int ans=n;
for(int i=2;i<=sqrt(n);i++)//2~ √n 求素因子
{
if(n%i==0)// 求素因子
{
ans=ans/i*(i-1); ///通项公式求解欧拉函数值
while(n%i==0) // 每个素因子只计算一次
n/=i;
}
}
if(n>1) ans=ans/n*(n-1); //当n为素数时
return ans;
}
int main()
{
int n;
while(cin>>n)///测试
{
cout<<euler(n)<<endl;
}
return 0;
}
2.编程实现模重复平方运算（求b^n (mod m)）
image.png
方法一：非递归（模幂算法）
#include<iostream>
#include<cmath>
using namespace std;
int euler(int n)//求n的欧拉值
{
int ans=n;
for(int i=2;i<=sqrt(n);i++)//2~ √n 求素因子
{
if(n%i==0)// 求素因子
{
ans=ans/i*(i-1); ///通项公式求解欧拉函数值
while(n%i==0) // 每个素因子只计算一次
n/=i;
}
}
if(n>1) ans=ans/n*(n-1); //当n为素数时
return ans;
}
int powerMod(int b,int n,int m){//模平方算法
int r;
r=n%euler(m);
n=r;
int a=1;//存放计算结果，初始化为1
int i,k=0,num=n;
while(num){//计算指数二进制位数k
num=num>>1;//将num右移1位（也即除以2），然后再将结果赋值给num.等同 num=num/2;
++k;//num的二进制右移一位
}
for(i=0;i<k;i++){
if((n>>i)&1)//取二进制的第i位，然后和1进行与运算（判断i位是否为1）
{a=a*b%m;}//二进制位为1时操作
b=b*b%m;// 二进制位为1和0时操作
}
return a;
}
int main(){
int b,n,m;
cout<<"请分别输入底数b,指数n,模m：";
cin>>b>>n>>m;
cout<<"b^n(mod m)="<<powerMod(b,n,m);
return 0;
}
image.png
方法二：递归
递归公式： b^n(mod m)=b* (b^(n-1) (mod m)) (mod m)
#include<iostream>
using namespace std;
int powerMod(int b,int n,int m){ //递归公式： b^n(mod m)=b* (b^(n-1) (mod m)) (mod m)
if(0==n)
return 1;
return b*powerMod(b,n-1,m)%m;
}
int main(){
int b,n,m;
cout<<"请分别输入底数b,指数n,模m：";
cin>>b>>n>>m;
cout<<"b^n(mod m)="<<powerMod(b,n,m);
return 0;
}
image.png
网友评论