Java high-order power modulus + product function + inverse method

Title meaning: The sum (S) of all positive factors of 2004^x is the remainder of 29; output the result;

Original question link

Title analysis: Analysis reference source: Click to open The factors linking

and

are 1,2,3,6; the sum of the factors of 6 is s(6)=1 2 3 6=12;

The factors of 20 are 1,2,4,5,10,20; the sum of the factors of 20 is s(20)=1 2 4 5 10 20=42; the factors of

2 are 1,2; 2 The sum of the factors of is s(2)=1 2=3;

The factors of 3 are 1,3; The sum of the factors of 3 is s(3)=1 3=4;

4 The sum of the factors is
s(4)=1 2 4=7; The sum of the factors of

5 is
s(5)=1 5=6;

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

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

Is this a coincidence?

Look at s(50)=1 2 5 10 25 50=93=3*31=s(2)*s(25),s(25)=1 5 25=31.

This is called the product function in number theory. When gcd(a,b)=1, s(a*b)=s(a)*s(b);

If p is a prime number

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

Example hdu1452 Happy2004

Calculate factor sum 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)//According to (1)

b=s(3^X)= (3^(X 1)-1)/2//According to (1)

c=s(22^X)= (22^(X 1)-1)/21//According to (1)

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

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

b^(-1) is the inverse element of
b (%p). The inverse element of

2 is 15 ()), because 2*15=30 % 29=1 % 29

The inverse element of

21 is 18 ()), because 21*18=378% 29 =1 % 29

Therefore

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

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

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

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

Data expansion: 1.

Higher power Quick Model Link
2. Jacking Function : The Jiming Function of the Division Theory: For a positive integer n f(n), if f(1)=1, and when
a,b are relatively prime, f(ab)=f(a )f(b), it is called a product function in number theory. like                                                                                                                                                                                                                                       may be said to be complete. If
n is expressed as a prime factor decomposition formula;               3. Find the inverse element:
                         
When calculating (a/b)%Mod, it is often necessary to calculate b%Mod first Inverse element p (the condition for b to have an inverse element is gcd(b,Mod)==1, obviously prime numbers must have inverse elements), and then get the result c from (a*p)%Mod
. Here
the inverse element p of b satisfies (b*p)%Mod=1. Let’s briefly prove it first:
(a/b)%Mod=c; (b*p)%Mod=1; ==》 (a/b)*(b*p) %Mod=c; == 》 (a*p)%Mod=c;

From the above we can see the correctness of the conclusion, of course b needs to be a factor of a . Next, we need to know how to calculate the inverse element p based on b and Mod. Everyone should be familiar with the extended Euclidean algorithm, which is used to find a set of solutions (x, y) when a and b are known, such that a*x b*y=1. x and y are respectively the inverse element of a modulo b and the inverse element of b modulo a, which can be verified by modulo b or a.

The reasons are explained below:

Modulo m multiplicative inverse element

Definition: For integers a, m, if there is an integer b, it satisfies ab ≡ 1(mod m), then it is said that b is the multiplicative inverse of a modulo m.

Theorem: The necessary and sufficient condition for a to have a multiplicative inverse modulo m is gcd(a,m) = 1

Sufficiency:

because

##gcd(a,m) = 1

According to Euler’s theorem, there is

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

Therefore

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

So there is a modulo m multiplicative inverse of a, that is, a^( φ(m)-1)

Necessity:

Suppose there is a multiplicative inverse of a modulo m that is b, then

ab ≡ 1 (mod m)

##so

ab = km 1

##so

1 = ab - km

By Euclid Obtain the theorem, there is

gcd(a,m) = 1

It is known from the theorem:

##For ax by = 1, it can be seen that x is a The multiplicative inverse modulo b, y is the multiplicative inverse of b modulo a.

Conversely, to calculate the multiplicative inverse of a modulo b is equivalent to finding the smallest positive integer solution of x for ax by = 1, Thus it can be solved into a linear indefinite equation.

Specific reference: http://blog.csdn.net/synapse7/article/details/9901195 Call ExtGcd (b, Mod, x, y), x is the inverse element p of b%Mod.

There is another way to find the inverse element p of b%Mod, that is, p=b^(Mod-2)%Mod, because b^(Mod-1)%Mod=1 (Mod needs to be a prime number here). Error analysis: 1: if(y&1)ans*=x);//Ans=x*x) in the test by mistake) 2. The data type must be __int64,

Code implementation:

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

The above is the detailed content of Java high-order power modulus + product function + inverse method. For more information, please follow other related articles on the PHP Chinese website!