上课作业(7)——＃598. 取余运算(mod)

目录

Description

Format

Input

Output

Samples

输入数据 1

输出数据 1

Limitation

方法一：

错误程序：

方法二：

AC程序

Description

输入 b，p，k 的值，求 b^p mod k 的值。其中 b，p，k*k 为长整形数。

Format

Input

输入 3 个整数 b,p,k。

Output

求 b^p\ mod~ kbp mod k 的值。

Samples

输入数据 1

2 10 9

输出数据 1

2^10 mod 9=7

Limitation

1s, 1024KiB for each test case.

方法一：

用pow函数再加个取余运算直接快速求出答案，结果40分，数据超了最大类型的限额(unsigned long long)。

错误程序：

#include<bits/stdc++.h>
using namespace std;
int main(){
	long a,b,c;
	unsigned long long ans;
	cin>>a>>b>>c;
	ans=pow(a,b);
	ans%=c;
	cout<<a<<'^'<<b<<" mod "<<c<<'='<<ans;
	return 0;
}

方法二：

用快速幂并在while循环里穿插着取余运算的代码，因为还要输出原来的数据并且循环后数据会改变所以要先把输出的模板输出，最后再输出最终答案。

AC程序：

#include<bits/stdc++.h>
using namespace std;
long a,b,c;
unsigned long long ans=1;
int main(){
    cin>>a>>b>>c;
    cout<<a<<'^'<<b<<" mod "<<c<<'='; 
    while(b){
    	if(b%2==1){
    		ans*=a;
    		ans%=c;
    	}
    	b/=2;
    	a*=a;
    	a%=c;
	}
	ans%=c;
	cout<<ans;
    return 0;
}