d472 - 算術基本原理
題目描述
題目要求計算算術基本原理所表示的 N mod 76543。輸入為 k 序列，其中 k_i 為第 i 個質數的指數。輸出為 N mod 76543。
解題思路
程式碼首先使用埃拉托斯特尼篩法找出 10000 以內的質數。然後，程式讀取輸入的 k 序列，對於序列中的每個質數，計算質數的 n 次方，並將結果累乘，最後取模 76543。模運算使用快速冪演算法來提高效率。
複雜度分析
- 時間複雜度: O(N log log N + L log N)，其中 N 是質數篩選的上限 (10000)，L 是輸入序列的長度。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)，快速冪的時間複雜度為 O(log N)，因此總時間複雜度為 O(N log log N + L log N)。
- 空間複雜度: O(N)，主要用於儲存質數陣列。
程式碼
#include <iostream>
using namespace std;
long long int p[10001]={1,1},it,pri[2001],bm;
long long int mod(long long int b,long long int p,long long int m){
if(p==0)return 1;
if(p==1)return bm;
bool o=p&1;
p>>=1;
long long int tmp=mod(b,p,m);
if(o)
return tmp*tmp*b%m;
else
return tmp*tmp%m;
}
int main(){
long long int ans=1,n;
for(int i=2;i<=100;++i)
for(int j=i+i;j<=10000;j+=i)
p[j]=1;
for(int i=0;i<=10000;++i)
if(p[i]==0)
pri[it++]=i;
it=0;
while(cin >> n){
bm=pri[it]%76543;
ans*=mod(pri[it++],n,76543);
ans%=76543;
}
cout << ans;
}