Modulus kuasa pesanan tinggi Java + fungsi produk + kaedah songsang

Maksud tajuk: Cari baki jumlah (S) semua faktor positif tahun 2004^x hingga 29; sumber: Klik untuk membuka Pautan

jumlah faktor

Faktor 6 ialah 1,2,3,6 jumlah faktor 6 ialah s(6)=1+2+3+; 6=12;

Faktor bagi 20 ialah 1,2,4,5,10,20 hasil tambah bagi faktor 20 ialah s(20)=1+2+4+5+10+ 20=42;

2 Faktor bagi ialah 1,2 hasil tambah bagi faktor 2 ialah s(2)=1+2=3; ,3; jumlah faktor bagi 3 ialah s(3)=1+3 =4; 7; Jumlah faktor bagi

5 ialah

s(5)=1 +5=6;

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

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

Adakah ini satu kebetulan?

Lihat lagi s(50)=1+2+5+10+25+50=93=3*31=s(2)*s(25),s(25)=1+5+ 25=31.

Ini dipanggil fungsi hasil dalam teori nombor Apabila gcd(a,b)=1, s(a*b)=s(a)*s(b);

.

Jika p ialah nombor perdana

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

Contoh hdu1452 Happy2004

Kira jumlah faktor 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)//Mengikut (1)

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

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

% algoritma

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

% algoritma

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

b^(-1) ialah unsur songsang bagi

b (%p) Unsur songsang bagi

2 ialah 15 ()) , kerana 2*15=30 % 29=1 % 29

Unsur songsang bagi 21 ialah 18 ()), kerana 21*18=378% 29 =1 % 29

Oleh itu

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;

Peluasan data:

1.

Pautan pemodelan pantas kuasa dimensi tinggi

2. Fungsi: fungsi aritmetik

untuk integer positif

n

f(n), jika f(1)=1, dan apabila

a,
b
agak perdana, f(ab
)=f( a )f(b) dipanggil fungsi produk dalam teori nombor. Jika
Untuk fungsi terkumpul f (n), walaupun A, B tidak saling berkualiti, terdapat juga f (ab) = f (a) f (b), yang dipanggil pengumpulan lengkap. Jika n dinyatakan sebagai formula penguraian faktor utama p (syarat untuk b mempunyai unsur songsang ialah gcd(b,Mod)==1, jelas nombor perdana mesti mempunyai unsur songsang), dan kemudian dapatkan hasil c daripada (a*p)%Mod . Di sini unsur songsang p bagi b memenuhi (b*p)%Mod=1. Mari kita buktikan secara ringkas dahulu: (a/b)%Mod=c; (b*p)%Mod=1 ==》 (a/b)*(b*p) %Mod=c; 》 (a*p)%Mod=c;
Daripada perkara di atas kita dapat melihat ketepatan kesimpulan, sudah tentu b perlu faktor a. Seterusnya, kita perlu tahu cara mengira unsur songsang p berdasarkan b dan Mod. Semua orang harus biasa dengan algoritma Euclidean lanjutan, yang digunakan untuk mencari satu set penyelesaian (x, y) apabila a dan b diketahui, supaya a*x+b*y=1. x dan y masing-masing ialah unsur songsang modulo b dan unsur songsang bagi b modulo a, yang boleh disahkan oleh modulo b atau a.






Sebabnya dijelaskan di bawah:

Modulo songsang pendaraban m

Definisi: Untuk integer a, m, jika terdapat integer b, ia memenuhi ab ≡ 1(mod m), maka dikatakan bahawa b ialah songsangan darab bagi modulo m.

Teorem: Syarat yang perlu dan mencukupi untuk kewujudan modulo m songsang darab a ialah gcd(a,m) = 1

Kecukupan:

Sebab

gcd(a,m) = 1

Mengikut teorem Euler, terdapat

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

Oleh itu

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

Jadi terdapat invers modulo m darab bagi a , iaitu, a^( φ(m)-1)

Keperluan:

Katakan terdapat songsangan darab bagi modulo m iaitu b, kemudian

ab ≡ 1 (mod m)

jadi

ab = km +1

Jadi

1 = ab - km

Oleh Teorem Euclidean Reed mempunyai

gcd(a,m) = 1

Daripada teorem:

Untuk ax + by = 1, kita boleh lihat bahawa x ialah songsangan darab bagi modulo b, dan y ialah songsangan darab bagi b modulo a.

Sebaliknya, untuk mengira songsangan darab bagi modulo b adalah bersamaan dengan mencari penyelesaian integer positif terkecil bagi x untuk ax + by = 1 , dengan itu mengubahnya menjadi persamaan tak tentu linear dan menyelesaikannya.

Rujukan khusus: http://blog.csdn.net/synapse7/article/details/9901195 Panggil ExtGcd (b, Mod, x, y), x ialah unsur songsang p b%Mod.
Terdapat satu lagi cara untuk mencari unsur songsang p b%Mod, iaitu, p=b^(Mod-2)%Mod, kerana b^(Mod-1)%Mod=1 (Mod perlu menjadi nombor perdana di sini). Analisis ralat: 1: if(y&1)ans*=x%29;//Tersilap diuji ans=x*x%292 Jenis data mesti menggunakan __int64,

Pelaksanaan kod:

.

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

Atas ialah kandungan terperinci Modulus kuasa pesanan tinggi Java + fungsi produk + kaedah songsang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!