BZOJ_1004カルズ
1545 ワード
1.テーマに関するものタグ: タイトルアドレス:http://www.lydsy.com/JudgeOnline/problem.php?id=1004 テーマ:中国語の問題. 2.考え方は、ベースのPolyaカウントを比較する. Burnide引理＋Kバックパック＋乗算逆元を利用する.知らないうちにKバックができます. 前の二つのネットには資料がたくさんあります.掛け算の逆元に重点を置いています. とりあえずユークリッドの拡張について話してください. コードは以下の通りです. 上記の知識があれば、(a/b)%pの値について議論することができます. まず定義を見にきます. がa・k＝1(mod p)を満たすk値はaのpに関する乗算逆元である. はなぜ乗算元を使うのですか? 私たちはp%の値を要求し、aが大きいので、a/bの値を直接的に求めることができない場合、乗算逆元を使用します. pに関するb乗算逆元kを求めることにより、aをk再モードp、すなわち(a・k)%pに乗せることができます.その結果は(a/b)mod pと等価である. 証明書は以下の通りです. で、kの値はexgcdを呼べばいいです.ただし、kはマイナスかもしれませんので、Pをどんどん入れてください. コードは以下の通りです. 注意問題の中にはちょっとお父さんのところがあります.(1,2,3…n-1,n)この置き換えはありません.実は私は太菜です.
クリックしてコードを表示します
Polya a·X1 + b·Y1 = gcd(a, b) b·X2 + (a % b)·Y2 = gcd(b, a % b)を設けると、gcd(a, b) = gcd(b, a % b)がa % b = a-(a/b)·bを整理し、a·X1 + b·Y1 = b·X2 + (a-(a/b)·b)·Y2 a·X1 + b·Y1 = a·Y2 + b·[X2-(a/b)]·Y2を得ることができるので、X1 = Y2 , Y1 = X2-(a/b)·Y2を整理する.void exgcd(int a, int b, int &x, int &y) {
if (b == 0) {x = 1; y = 0; return;}
exgcd(b, a%b, x, y);
int t = x; x = y; y = t-a/b*y;
}
b·k ≡ 1 (mod p)によれば、b·k = p·x + 1がkをk = (p·x + 1) / bの原形(a·k) mod pに代入することができるので、元の形は= (a·(p·x + 1) / b) % pに等しい.exgcd(b, p, k, y);
while (k <= 0) k += p;
クリックしてコードを表示します