Java高次べき乗率+積関数+逆法

タイトルの意味: 2004^x のすべての正の要素の合計 (S) は 29 の余りです; 結果を出力します;

元の質問リンク

タイトル分析: 分析参照元: クリックして開きます

と

を結ぶ因数は 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);

If p が a素数

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

Example 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 による。(a* b) %p= ( a%p) *(b%p)

% アルゴリズム

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

b^(-1) は

b (%p) の逆要素です。2*15=30 % 29 であるため、

2 の逆要素は 15 ()) です。 =1 % 29

21 の逆元は 18 ()) です。21*18=378% 29 =1 % 29

したがって、

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;

データ展開:

1.
高出力クイック モデル リンク

2. ジャッキング関数 : 除算理論のジミング関数: 正の整数の場合 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 です。明らかに素数には逆要素が必要です)、次に (a*p)%Mod から結果 c を取得します。
。ここで
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 は次のようにする必要があります。の係数。次に、b と Mod に基づいて逆要素 p を計算する方法を知る必要があります。拡張ユークリッド アルゴリズムについては誰もがよく知っているはずです。このアルゴリズムは、a*x b*y=1 など、a と b が既知の場合に、一連の解 (x、y) を見つけるために使用されます。 x と y はそれぞれ、b を法とする a の逆要素と a を法とする b の逆要素であり、b または a を法として検証できます。

#その理由は以下で説明されています:

##モジュロ m 乗法逆元

##定義: 整数 a、m に対して、整数 b があれば、それは満たされます。 ab ≡ 1(mod m) の場合、b は a を法とする逆乗であると言われます。

定理: a が乗法逆法 m を持つための必要十分条件は gcd(a,m) = 1

十分性:

理由

gcd(a,m) = 1

##オイラーの定理によれば、

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

#したがって

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

したがって、a の法 m の逆乗、つまり a が存在します。 ^( φ(m)-1)

必要性:

# b を法とする m の逆乗があると仮定すると、

##ab ≡ 1 (mod m)

so

ab = km 1

##だから

1 = ab - km

Euclid によって、定理、

gcd(a,m) = 1

# があります。

#これは定理からわかります:

##ax by = 1 の場合、次のことがわかります。 x は b を法とする乗法逆数であり、y は a を法とする b の逆数です。

逆に、モジュロ b の逆乗を計算することは、ax に対する x の最小の正の整数解を = 1 で見つけることと同じです。それは線形不定方程式に解くことができます。

具体的な参照: 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);//Ans=x*x) (テストで誤って) 2. データ型は __int64,

でなければなりません コード実装:

うわー

以上がJava高次べき乗率+積関数+逆法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。