Java 고차 거듭제곱 계수 + 곱함수 + 역법

제목 의미: 2004^x에서 29까지의 모든 긍정적 요인의 나머지(S)를 구하고 결과를 출력합니다.

원래 질문 링크

질문 분석: 분석 참조 소스: 링크를 열려면 클릭하세요.

factors

6의 인수는 1,2,3,6이고, 6의 인수의 합은 s(6)=1+2+3+6=12입니다.

20의 인수는 1,2,4입니다. ,5,10,20; 20의 인수합은 s(20)=1+2+4+5+10+20=42입니다.

2의 인수합은 1,2입니다. 2는 s(2)=1+2=3입니다.

3 의 인수 합은 1,3입니다. 3의 인수 합은 s(3)=1+3=4입니다.

4의 인수 합은
입니다. s(4)=1+2+4=7;

5의 인수 합은
s(5)=1+5=6;

s(6)=s(2)*s(3)=입니다. 3*4=12;

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

이거 우연인가요?

다시 보세요 s(50)=1+2+5+10+25+50=93=3*31=s(2)*s(25), s(25)=1+5+25=31.

이를 정수론에서는 곱함수라고 합니다. gcd(a,b)=1일 때 s(a*b)=s(a)*s(b);

p가 소수인 경우

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

예제 hdu1452 Happy2004

계산 인수 합계 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)//(1)에 따르면

b=s(3^X)= (3^ (X+1 )-1)/2//(1)에 따르면

c=s(22^X)= (22^(X+1)-1)/21//(1)에 따르면

% 알고리즘
1. %p= ( a%p) *(b%p)

% 알고리즘
2 (a/b) %p= ( a *b^(-1)%p )

b ^(-1)은
b(%p)의 역원소입니다.

2의 역원소는 15())입니다. 왜냐하면 2*15=30 % 29=1 % 29 의 역원소이기 때문입니다.

21은 18())이므로 21*18=378% 29 =1 % 29

따라서

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 ;

데이터 확장: 1.

고차 전력 빠른 모듈로 링크
                                                                                                        생산성 함수 : 정수 이론의 생산성 함수: 양의 정수에 대한 산술 함수 n f(n), f(1)=1이고
a,b이 상대적으로 소수인 경우 f(ab)=f(a)f(b)는 정수론에서 호출됩니다. 제품 기능입니다. 만약 ~                                                                                            완전하다고 할 수 있습니다.
n을 소인수 분해 공식으로 표현하면                 3. 역원소 찾기:
                     
(a/b)%Mod를 계산할 때 b%Mod의 역원소 p를 먼저 계산해야 하는 경우가 많습니다( b가 역원소를 갖는 조건 gcd(b,Mod)==1입니다. 분명히 소수는 역원소를 가져야 합니다. 그러면 결과 c는 (a*p)%Mod
에 의해 얻어집니다. 여기서
b의 역요소 p는 (b*p)%Mod=1을 만족합니다. 먼저 간단히 증명해 보겠습니다.
(a/b)%Mod=c; (b*p)%Mod=1; ==》 (a/b)*(b*p) %Mod=c; a*p)%Mod=c;

위에서 우리는 결론의 정확성을 볼 수 있습니다. 물론 b는 a의 인수가 되어야 합니다. 다음으로 b와 Mod를 기반으로 역원소 p를 계산하는 방법을 알아야 합니다. 모든 사람은 a*x+b*y=1과 같이 a와 b가 알려져 있을 때 일련의 해(x, y)를 찾는 데 사용되는 확장된 유클리드 알고리즘에 익숙해야 합니다. x와 y는 각각 모듈로 b의 역 요소이고 모듈로 a의 역 요소이며, 이는 모듈로 b 또는 a로 검증할 수 있습니다.

이유는 아래에 설명되어 있습니다.

modulo m 곱셈 역

정의: 정수 a , m, 정수 b가 있으면 만족 ab 1 (mod m)이면 b는 모듈로 m의 곱셈의 역수라고 합니다.

정리: 곱셈의 역 모듈로 m이 존재하기 위한 필요 충분 조건은 gcd(a,m) = 1

충분함:

왜냐하면

gcd(a,m) = 1

오일러의 정리에 따르면

a^ψ(분) DF 1( mod m : 역위안, 즉 a^(Φ(m)-1)

필수:

ㅋㅋㅋ 그러니까

ab = km +1

So

1 = ab - km

결정,

gcd(a,m) = 1

정리에서 알 수 있습니다.

ax + by = 1의 경우 x는 a의 곱셈의 역수임을 알 수 있습니다. 모듈로 b, y는 b 모듈로 a의 곱셈의 역수입니다.

모듈로 b의 곱셈 역원을 계산하는 것은 ax + by = 1에 대해 x의 가장 작은 양의 정수 해를 찾아 이를 선형 부정 방정식으로 푸는 것과 같습니다.

특정 참조: http://blog.csdn.net/synapse7/article/details/9901195 ExtGcd(b, Mod, x, y)를 호출하면 x는 b%Mod의 역요소 p입니다.

b%Mod의 역원소 p, 즉 p=b^(Mod-2)%Mod를 찾는 또 다른 방법이 있습니다. 왜냐하면 b^(Mod-1)%Mod=1(Mod는 소수여야 하기 때문입니다) 여기). 오류 분석: 1: if(y&1)ans*=x%29;//ans=x*x%292를 잘못 테스트했습니다. 데이터 유형은 __int64를 사용해야 합니다.

코드 구현:

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

위 내용은 Java 고차 거듭제곱 계수 + 곱함수 + 역법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!