題目請參考 https://zerojudge.tw/ShowProblem?problemid=l048.
這題首先要解決的是n的t次方求mod a1,由於n可能非常大,可以先把n mod a1先求出來,假設r=n mod a1, 答案就等同於計算 r的t次方 mod a1.
下面是計算n mod a1, 我把字串n用直式除法來求餘數, 由於unsigned long long介於0 到 18,446,744,073,709,551,615之間,所以我把字串n轉成數字時,控制在小於1,800,000,000,000,000,000時可以繼續增加位數.這樣在增加位數後也不會超出範圍,可以直接求出餘數.
char n[1000];//n以字串形式放在陣列中
unsigned long long n_mod(unsigned long long a){
int offset=0;
unsigned long long number=0;
while(n[offset]){
unsigned long long number2=number*10+n[offset]-'0';
if(number2 <= 1800000000000000000){
number=number2;
}else{
number=(number%a)*10+n[offset]-'0';
}
offset++;
}
return number%a;
}由於r比n小多了, 而且r<a1,所以r的t次方mod a1可以直接用unsigned long long來計算mod.
int t;
scanf("%s %d",n,&t);
unsigned long long a1;
scanf("%lld",&a1);
unsigned long long r=n_mod(a1);
//計算r的t次方 mod a1
unsigned long long r2=r;
for(int i=1;i<t;i++){
r2=(r2*r)%a1;
}
再來就是要處理mod a2)*a2 mod a3)*a3 … mod at)*at.
unsigned long long a2;
for(int i=1;i<t;i++){
scanf("%lld",&a2);
r2=(r2*a1)%a2;
a1=a2;
}
printf("%lld", r2*a2);以下是完整程式. AC耗時40ms.
#include <iostream>
using namespace std;
char n[1000];//n以字串形式放在陣列中
unsigned long long n_mod(unsigned long long a){
int offset=0;
unsigned long long number=0;
while(n[offset]){
unsigned long long number2=number*10+n[offset]-'0';
if(number2 <= 1800000000000000000){
number=number2;
}else{
number=(number%a)*10+n[offset]-'0';
}
offset++;
}
return number%a;
}
int main() {
int t;
scanf("%s %d",n,&t);
unsigned long long a1;
scanf("%lld",&a1);
unsigned long long r=n_mod(a1);
//計算r的t次方 mod a1
unsigned long long r2=r;
for(int i=1;i<t;i++){
r2=(r2*r)%a1;
}
unsigned long long a2;
for(int i=1;i<t;i++){
scanf("%lld",&a2);
r2=(r2*a1)%a2;
a1=a2;
}
printf("%lld", r2*a2);
return 0;
}
