C言語アルゴリズム

【数論】Sumdiv（X ^ Y因子の合計を求める）



Number Theory Sumdiv



2つの自然数AとBを考えます。SをA ^ Bのすべての自然約数の合計とします。 Sモジュロ9901（Sを9901で除算した残りの部分）を決定します。
入力
唯一の行には、2つの自然数AとB（0<= A,B <= 50000000)separated by blanks.
出力
出力の唯一の行には、9901を法とするSが含まれます。
サンプル入力
2. 3
サンプル出力
15
ヒント
2 ^ 3 = 8。
8の自然除数は次のとおりです：1、2、4、8。それらの合計は15です。
15モジュロ9901は15です（出力する必要があります）。

題名：
X ^ Yの因数和を求めると、結果は9901を法とします。



思考分析：
因子の合計を見つけるためのテンプレート質問です。素数ふるい、合成数分解、合同定理、高速乗算、高速電力、および因子の合計の式を使用します。この質問を行うには、いくつかの落とし穴があります。

  1. 高速パワーを最適化するために高速乗算を使用する必要があります。そうしないと、長時間バーストします。
  2. この質問は、逆元では実行できません。法9901は素数ですが、aが9901の倍数の場合、互いに素にすることはできません。合同定理の除算式を使用する必要があります。

ACコードを真下に置きます。



#include #include #include #define ll long long using namespace std const int N = 200000 ll prime[N] int vis[N] int t ll fast_mul(ll x,ll y,ll mod){ //Fast multiplication (x*y modulo to prevent overflow and speed up) ll res=0 while(y){ if(y&1) res=(res+x)%mod x=(x+x)%mod y /= 2 } return res } ll pow_mod(ll x,ll y,ll mod){ //Fast multiplication optimization fast power ll res=1 while(y){ if(y&1) res=fast_mul(res,x,mod) x=fast_mul(x,x,mod) y /= 2 } return res } void isPrime() //Prime sieve { t=0 memset(vis,0,sizeof(vis)) memset(prime,0,sizeof(prime)) for(ll i=2i<Ni++) { if(!vis[i]) { prime[t++]=i for(ll j=i*ij<Nj+=i) vis[j]=1 } } } //factor[i][0]=pi,factor[i][1]=ai ll factor[100][2] ll cnt //cnt represents the number of prime factors void splitPrime(ll x) //Decompose prime factors { cnt=0 ll t=x for(int i=0prime[i]<=t/prime[i]i++) { factor[cnt][1]=0 while(t%prime[i]==0) //Divisible by prime numbers { factor[cnt][0]=prime[i] while(t%prime[i]==0) //Calculate the number of divisions by a prime number as the power of the prime number { factor[cnt][1]++ t/=prime[i] } cnt++ } } if(t!=1) //t!=1 means t is a prime number { factor[cnt][0]=t factor[cnt][1]=1 cnt++ } } ll sum_factor(ll x, ll y, ll c) //Find the sum of the factors. s(n) = (1+p^1+p^2+...p^e)*s(n') = (p^(e+1)-1) / (p-1) * s( n') { //Let g(p, e) = (p^(e+1)-1) / (p-1), then s(n) = g(p1, e1) * g(p2, e2) * .. . * g(pk, ek) if(x == 0) return 0 splitPrime(x) ll sum = 1 for(int i = 0i < cnti++) { ll b = factor[i][0]-1 ll m = b*c ll a = pow_mod(factor[i][0],y*factor[i][1]+1,m)-1 ll tmp = a/b%c sum *= tmp%c sum = (sum+c)%c } return sum } int main() { isPrime() ll A,B while(~scanf('%lld%lld',&A, &B)) { printf('%lld ',sum_factor(A,B,9901)) } return 0 }

補足：tmpアルゴリズムの説明について
画像