Module de puissance Java d'ordre élevé + fonction produit + méthode inverse

Signification du titre : trouvez le reste de la somme (S) de tous les facteurs positifs de 2004 ^ x à 29 ; affichez le résultat

Lien de la question originale

Analyse de la question : Source de référence de l'analyse : Cliquez pour ouvrir le lien

facteurs ; et

facteurs de 6 est 1,2,3,6 ; la somme des facteurs de 6 est s(6)=1+2+3+6=12 ; les facteurs de

20 sont 1,2,4 ; ,5,10,20 ; les facteurs de 20 La somme est s(20)=1+2+4+5+10+20=42 ; les facteurs de

2 sont 1,2 ; 2 est s(2)=1+2=3;

3 Les facteurs de sont 1,3 ; la somme des facteurs de 3 est s(3)=1+3=4 ; la somme des facteurs de

4 est
s(4)=1+2+4=7 ; la somme des facteurs de

5 C'est
s(5)=1+5=6;

s(6)=s(2)*s(3)= 3*4=12;

s(20)=s(4)*s( 5)=7*6=42;

Est-ce une coïncidence ?

Regardez à nouveau s(50)=1+2+5+10+25+50=93=3*31=s(2)*s(25), s(25)=1+5+25=31.

C'est ce qu'on appelle la fonction produit en théorie des nombres. Lorsque pgcd(a,b)=1, s(a*b)=s(a)*s(b);

Si p est un nombre premier

s. (p^ n)=1+p+p^2+...+p^n=(p^(n+1)-1) /(p-1) (1)

Exemple hdu1452 Happy2004

Calculer somme des facteurs s (2004^X) mod 29,

2004=2^2 *3 *167

s(2004^X) ) = (s(2^2X))) *(s(3^X)) ) * ( s(167^X)))

167)=22;

s(2004^X) ) = (s(2^2X))) *(s(3^X))) * (s (22^ X)))

a=s(2^2X)=(2^(2X+1)-1)//D'après (1)

b=s(3^X)= (3^ (X+1 )-1)/2//Selon (1)

c=s(22^X)= (22^(X+1)-1)/21//Selon (1)

% algorithme
1. (a*b) %p= ( a%p) *(b%p)

% algorithme
2 (a/b) %p= ( a *b^(-1)%p. )

b ^(-1) est l'élément inverse de
b (%p). L'élément inverse de

2 est 15 ()), car 2*15=30 % 29=1 % 29 L'élément inverse de

21 vaut 18 ()) , car 21*18=378% 29 =1 % 29

Donc

a=(powi(2,2*x+1,29)-1)%29;

b =(powi(3,x+ 1,29)-1)*15 %29;

c=(powi(22,x+1,29)-1)*18 %29;

ans=（a*b ）% 29*c % 29 ;

Extension des données : 1.

Lien modulo rapide de puissance d'ordre élevé
                                                                                                                              Fonction de productivité  : Fonction de productivité en théorie des nombres : une fonction arithmétique pour les entiers positifs n f(n), si f(1)=1, et quand
a,b sont relativement premiers, f(ab)=f(a)f(b) est appelé en théorie des nombres C'est une fonction du produit. Si Pour une fonction accumulée f (n), même si A, B ne sont pas mutuellement de qualité, il existe aussi f (ab) = f (a) f (b), ce qu'on appelle accumulation complète. Si
n est exprimé sous la forme d'une formule de décomposition en facteur premier ;                3. Trouvez l'élément inverse :
                      
Lors du calcul de (a/b)%Mod, il est souvent nécessaire de calculer d'abord l'élément inverse p de b%Mod (le condition pour que b ait un élément inverse C'est pgcd(b,Mod)==1, évidemment les nombres premiers doivent avoir des éléments inverses), et alors le résultat c est obtenu par (a*p)%Mod
. Ici
l'élément inverse p de b satisfait (b*p)%Mod=1. Prouvons-le brièvement d'abord :
(a/b)%Mod=c; (b*p)%Mod=1; ==》 (a/b)*(b*p) %Mod=c ==》 ( a*p)%Mod=c;

D'après ce qui précède, nous pouvons voir l'exactitude de la conclusion. Bien sûr, b doit être un facteur de a. Ensuite, nous devons savoir comment calculer l’élément inverse p en fonction de b et Mod. Tout le monde devrait être familier avec l'algorithme euclidien étendu, qui est utilisé pour trouver un ensemble de solutions (x, y) lorsque a et b sont connus, tels que a*x+b*y=1. x et y sont respectivement l'élément inverse de a modulo b et l'élément inverse de b modulo a, ce qui peut être vérifié par modulo b ou a.

La raison est expliquée ci-dessous :

modulo m inverse multiplicatif

Définition : Pour les entiers a, m, s'il existe un entier b, Satisfaire ab ≡ 1 (mod m), alors on dit que b est l'inverse multiplicatif d'un modulo m.

Théorème : La condition nécessaire et suffisante pour l'existence d'un modulo inverse multiplicatif m est pgcd(a,m) = 1

Suffisance :

Parce que

gcd(a,m) = 1

D'après le théorème d'Euler, on a

a^φ(m) ≡ 1( mod m )

Donc

a * a^(φ(m)-1) mod m = 1

Il y a donc multiplication modulo m d'un Yuan inversé, c'est-à-dire a^(φ(m)-1)

Nécessité :

Supposons qu'il existe un inverse multiplicatif d'un modulo m qui est b, alors

#🎜🎜 ## 🎜🎜#

ab ≡ 1 (mod m)

#🎜 🎜#

so

ab = km +1

so

#🎜🎜 ## 🎜🎜#

1=ab - km

#🎜 🎜#D'après le théorème d'Euclide, nous avons

Il est connu grâce au théorème :

#🎜 🎜#

Pour ax + by = 1, on voit que x est l'inverse multiplicatif de a modulo b, et y est l'inverse multiplicatif de b modulo a.

À son tour, calculer l'inverse multiplicatif d'un modulo b équivaut à trouver ax + by = 1 Le plus petite solution entière positive de x, la transformant ainsi en une équation linéaire indéfinie à résoudre.

Référence spécifique : http://blog.csdn.net/synapse7/article/details/9901195 Appelez ExtGcd (b,Mod,x,y), x est l'élément inverse p de b%Mod .

Il existe une autre façon de trouver l'élément inverse p de b%Mod, c'est-à-dire p=b^(Mod-2)%Mod, car b^(Mod-1)%Mod=1 (Mod doit être un nombre premier ici). Analyse des erreurs : 1 : if(y&1)ans*=x%29;//Testé par erreur ans=x*x%292 Le type de données doit utiliser __int64,

Implémentation du code : #🎜 🎜#.

#include<cstdio>
#include<cstdlib>
using namespace std;
typedef __int64 ll;
ll  powmol(ll  x,ll  y)//高次幂取模的求x^ymod29
{
    ll  ans=1;
    x=x%29;
    while(y)
    {
        if(y&1)ans*=x%29;//y是奇数情况的处理；
        x=x*x%29;
        y>>=1;//
    }
    return ans;
}
int main()
{
    ll  x,a,b,c;
    while(scanf("%I64d",&x),x)
    {
        a=(powmol(2,2*x+1)-1)%29;
        b=(powmol(3,x+1)-1)*15%29;
        c=(powmol(22,x+1)-1)*18%29;
        printf("%I64d\n",(a*b)%29*c%29);
    }
    return 0;
}

Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!