【Théorie des nombres】 Sumdiv (Trouvez la somme des facteurs X ^ Y)

Number Theory Sumdiv



Considérons deux nombres naturels A et B. Soit S la somme de tous les diviseurs naturels de A ^ B. Déterminez S modulo 9901 (le reste de la division de S par 9901).
Saisir
La seule ligne contient les deux nombres naturels A et B, (0<= A,B <= 50000000)separated by blanks.
Production
La seule ligne de la sortie contiendra S modulo 9901.
Exemple d'entrée
2. 3
Exemple de sortie
quinze
Indice
2 ^ 3 = 8.
Les diviseurs naturels de 8 sont: 1,2,4,8. Leur somme est de 15.
15 modulo 9901 est égal à 15 (qui devrait être émis).

Titre:
Trouvez la somme des facteurs de X ^ Y, et le résultat est modulo 9901.



Analyse de la pensée:
est un modèle de question pour trouver la somme des facteurs. Il utilise la formule du tamis des nombres premiers, de la décomposition des nombres composites, du théorème de congruence, de la multiplication rapide, de la puissance rapide et de la somme des facteurs. Il y a plusieurs pièges à poser cette question:



  1. Besoin d'utiliser une multiplication rapide pour optimiser la puissance rapide, sinon elle éclatera longtemps longtemps
  2. Cette question ne peut pas être posée avec des éléments inverses. Bien que le module 9901 soit un nombre premier, lorsque a est un multiple de 9901, il ne peut pas être mutuellement premier. Besoin d'utiliser la formule de division du théorème de congruence.

Mettez le code AC directement ci-dessous.



#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 }

Supplément: À propos de l'explication de l'algorithme tmp
image