Java-Leistungsmodul höherer Ordnung + Produktfunktion + Umkehrmethode

Titelbedeutung: Ermitteln Sie den Rest der Summe (S) aller positiven Faktoren von 2004^x bis 29; geben Sie das Ergebnis aus.

Fragenanalyse: Analyse-Referenzquelle: Klicken Sie, um den Link

Faktoren zu öffnen und

Faktoren von 6 sind 1,2,3,6; die Summe der Faktoren von 6 ist s(6)=1+2+3+6=12; die Faktoren von

20 sind 1,2,4 ,5,10,20; die Summe ist s(20)=1+2+4+5+10+20=42; die Summe der Faktoren von

2 2 ist s(2)=1+2=3;

3 Die Faktoren von sind 1,3; die Faktorsumme von 3 ist s(3)=1+3=4; die Faktorsumme von

4 ist

s(4)=1+2+4=7; die Faktorsumme von

5 Es ist

s(5)=1+5=6;

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

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

Ist das ein Zufall?

Schauen Sie noch einmal: s(50)=1+2+5+10+25+50=93=3*31=s(2)*s(25), s(25)=1+5+25=31.

Dies wird in der Zahlentheorie als Produktfunktion bezeichnet. Wenn gcd(a,b)=1, s(a*b)=s(a)*s(b);

Wenn p eine Primzahl ist

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

Beispiel hdu1452 Happy2004

Berechnen Faktorsumme 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+1 )-1)/2//Gemäß (1)

c=s(22^X)= (22^(X+1)-1)/21//Gemäß (1)

% Algorithmus

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

% Algorithmus

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

b ^(-1) ist das inverse Element von
b (%p). Das inverse Element von

2 ist 15 ()), weil 2*15=30 % 29=1 % 29 Das inverse Element von

21 ist 18 ()), weil 21*18=378% 29 =1 % 29

Daher

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 ;

Datenerweiterung:

1.

High-Order-Power-Quick-Modulo-Link

                                                                                                                Produktivitätsfunktion

: Produktivitätsfunktion in der Zahlentheorie: eine arithmetische Funktion für positive ganze Zahlen
n
f(n), wenn f(1)=1 und wenn a
,b relativ teilerfremd sind, heißt f(ab)=f(
a)f(b) in der Zahlentheorie Es handelt sich um eine Produktfunktion. Wenn Für eine akkumulierte Funktion f (n) gibt es auch f (ab) = f (a) f (b), auch wenn A und B keine gegenseitige Qualität haben, was als vollständige Akkumulation bezeichnet wird. Wenn n als Formel zur Primfaktorzerlegung ausgedrückt wird; Bedingung dafür, dass b ein inverses Element hat. Es ist gcd(b,Mod)==1, offensichtlich müssen Primzahlen inverse Elemente haben), und dann wird das Ergebnis c durch (a*p)%Mod erhalten. Hier erfüllt das inverse Element p von b (b*p)%Mod=1. Lassen Sie es uns zunächst kurz beweisen: (a/b)%Mod=c; (b*p)%Mod=1; ==》 (a/b)*(b*p) %Mod=c; a*p)%Mod=c;



Aus dem Obigen können wir die Richtigkeit der Schlussfolgerung ersehen. Natürlich muss b ein Faktor von a sein. Als nächstes müssen wir wissen, wie man das inverse Element p basierend auf b und Mod berechnet. Jeder sollte mit dem erweiterten euklidischen Algorithmus vertraut sein, der verwendet wird, um eine Menge von Lösungen (x, y) zu finden, wenn a und b bekannt sind, sodass a*x+b*y=1 ist. x und y sind jeweils das inverse Element von a modulo b und das inverse Element von b modulo a, was durch Modulo b oder a verifiziert werden kann.

Der Grund wird unten erklärt:

modulo m multiplikativ invers

Definition: Für ganze Zahlen a , m, wenn es eine ganze Zahl b gibt, erfüllen Sie diese ab ≡ 1 (mod m), dann ist b die multiplikative Umkehrung eines Modulo m.

Theorem: Die notwendige und hinreichende Bedingung für die Existenz eines multiplikativen inversen Modulo m ist gcd(a,m) = 1

Suffizienz:

Denn

gcd(a,m) = 1

Nach dem Satz von Euler haben wir

a^φ(m) ≡ 1( mod m: umgekehrter Yuan, also a^(φ(m)-1)

Notwendigkeit:

Angenommen, es gibt eine multiplikative Umkehrung eines Modulo m, dann ist

ab ≡ 1 (mod m)

Also

ab = km +1

Also

1 = ab - km

bestimmt durch Euklid Vernünftig, ja

gcd(a,m) = 1

Aus dem Satz ist bekannt:

Für ax + by = 1 ist ersichtlich, dass x die multiplikative Umkehrung von a ist modulo b, y ist die multiplikative Umkehrung von b modulo a.

Die Berechnung der multiplikativen Umkehrung eines Modulo b ist wiederum gleichbedeutend damit, die kleinste positive ganzzahlige Lösung von x für ax + by = 1 zu finden und sie somit als lineare unbestimmte Gleichung zu lösen.

Spezifische Referenz: http://blog.csdn.net/synapse7/article/details/9901195 Rufen Sie ExtGcd (b, Mod, x, y) auf, x ist das inverse Element p von b%Mod.
Es gibt eine andere Möglichkeit, das inverse Element p von b%Mod zu finden, nämlich p=b^(Mod-2)%Mod, da b^(Mod-1)%Mod=1 (Mod eine Primzahl sein muss Hier). Fehleranalyse: 1: if(y&1)ans*=x%29;//Fälschlicherweise getestet ans=x*x%292 Der Datentyp muss __int64,

Code-Implementierung:

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

verwenden

Das obige ist der detaillierte Inhalt vonJava-Leistungsmodul höherer Ordnung + Produktfunktion + Umkehrmethode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!