POJ-高級機密
3217 ワード
タイトルの説明:
多くの場合、情報を暗号化する必要があります.特にインターネットの急速な発展に伴い、暗号化技術は特に重要である.
昔、ローマ人は戦争中に情報を伝えるために、置換法を頻繁に使って情報暗号化を行っていた.しかし、コンピュータの奇数が急速に発展している今日、この置換法は一撃に耐えられないように見えます.従って,暗号研究者は,同じように符号化しやすいが復号しにくい符号化規則を探そうとしている.
現在流行しているコードルールはRSAと呼ばれ、米マサチューセッツ工科大学の3人の教授が発明した.この符号化規則は,与えられた3つの正の整数a,b,cについて,aのb次方をcの残数で割った密なデモードアルゴリズムに基づいている.
あなたの任務はab mod cを計算するプログラムを書くことです
入力形式:
3つの正の整数a,b,cはテキストファイルSECRETから.DATに入力します.入力ファイルは1行のみで、3つの正の整数a,b,cの順で、3つの正の整数の間に1つのスペースで区切られ、1≦a,b出力フォーマット:
プログラムの実行結果をテキストファイルSECRETに書き込みます.DATでは、ファイルが1行しかないことが要求されます.
入出力サンプル
Sample input
Output for the input
2 6 11
9
問題の分析:
高速計算の乗方のアルゴリズム、aのb次方を求めます 2 2 2^13を計算すると、従来の方法では12回の乗算が必要であるが、最適化できる: 2*2の結果を保存してみてください.4*4*4*4*4*2と4*4の結果を保存します.16*16*16*2は全部で5回の演算で、それぞれ2*2、4*4、16*16*16*2と分析しています.私たちのアルゴリズムは半分も計算できない乗算です.このアルゴリズムを明らかにするために、もう一つの例を挙げます.2^7:2*2*2*2*2*2を2つに分けます.(2*2)*(2*2)*2を2*2で計算すれば、指数は2で割ることができますが、1つ残っていて、後で単独で乗ることができます.再び2つに分けて、指数を2:((2*2)*(2*2)*(2*2)*2で割って、実際に最後の括弧の中の2*2は今回また残って、それでは、後でそれを単独で乗じて今指数はすでに1になって、最終的な結果を計算することができます:16*4*2=128
[cpp] view plain copy
long my_power(long a,long b)
{
long r=1;//「残り」積の計算に使用
if(b==0)
return 1;
if(b<0)
return 0;
while(b>1)
指数が1 以下になるまで計算します.
if((b&1)!=0)//pが奇数かどうかを判断し、偶数の最低位は必ず0 である.
r*=a;//rが奇数の場合、「残り」をに乗じる
a *=a;//本体乗 b/=2;//指数を2で割った }
return r*a;//最後に本体と「残り」を乗じて結果とする.
} xのy次方対z型取り(x^y)mod zを求める:モングマリー高速べき乗型アルゴリズム X^YはY個のX乗算、すなわち積型分解式と見なすことができ、Y個のX乗算再型取りの過程を分解することができ、例えば:(17^25)%29は:((17*17)%29*(17*17)%29*......
上記のコードを用いてこのプロセスを最適化すると,有名なモングマリー高速べき乗モードアルゴリズムが得られる.
[cpp] view plain copy
long Montgomery(long a,long b,long m)
{
long r=1;
a %=m;
while(b>1)
{
if((b&1)!=0)
r = (r*a)%m;
a = (a*a)%m;
b/=2;
}
return (r*a)%m;
}
この問題に関する数学モデルおよび関連アルゴリズムは,[数論]大数を解くモードa^b%Rで既に言及されており,詳細なアルゴリズム解析が行われている.一つだけ言及しなければならないのは、初心者が犯しやすい間違いであり、abの結果を直接求めて余剰を取ることであり、理論的には可能であるが、コンピュータによるデジタル処理方式の特殊性、特にC++言語自体は大数の演算をサポートせず、現在最大で処理できるデータは64ビット2進数(_int 64タイプ)である.入力制限を見ると、この処理範囲をはるかに超えているはずなので、モジュールの性質でしかこの問題を作ることができません.
もちろん,O(b)のアルゴリズムとO(log 2 b)の2つの時間的複雑度のアルゴリズムはもちろん考慮できるが,問題に限定されたbはそれほど大きくない.もちろんO(log 2 b)のアルゴリズムをもっと熟知することをお勧めします.
多くの場合、情報を暗号化する必要があります.特にインターネットの急速な発展に伴い、暗号化技術は特に重要である.
昔、ローマ人は戦争中に情報を伝えるために、置換法を頻繁に使って情報暗号化を行っていた.しかし、コンピュータの奇数が急速に発展している今日、この置換法は一撃に耐えられないように見えます.従って,暗号研究者は,同じように符号化しやすいが復号しにくい符号化規則を探そうとしている.
現在流行しているコードルールはRSAと呼ばれ、米マサチューセッツ工科大学の3人の教授が発明した.この符号化規則は,与えられた3つの正の整数a,b,cについて,aのb次方をcの残数で割った密なデモードアルゴリズムに基づいている.
あなたの任務はab mod cを計算するプログラムを書くことです
入力形式:
3つの正の整数a,b,cはテキストファイルSECRETから.DATに入力します.入力ファイルは1行のみで、3つの正の整数a,b,cの順で、3つの正の整数の間に1つのスペースで区切られ、1≦a,b
プログラムの実行結果をテキストファイルSECRETに書き込みます.DATでは、ファイルが1行しかないことが要求されます.
入出力サンプル
Sample input
Output for the input
2 6 11
9
問題の分析:
高速計算の乗方のアルゴリズム、aのb次方を求めます
[cpp] view plain copy
long my_power(long a,long b)
{
long r=1;//「残り」積の計算に使用
if(b==0)
return 1;
if(b<0)
return 0;
while(b>1)
指数が1 以下になるまで計算します.
if((b&1)!=0)//pが奇数かどうかを判断し、偶数の最低位は必ず0 である.
r*=a;//rが奇数の場合、「残り」をに乗じる
a *=a;//本体乗 b/=2;//指数を2で割った }
return r*a;//最後に本体と「残り」を乗じて結果とする.
}
上記のコードを用いてこのプロセスを最適化すると,有名なモングマリー高速べき乗モードアルゴリズムが得られる.
[cpp] view plain copy
long Montgomery(long a,long b,long m)
{
long r=1;
a %=m;
while(b>1)
{
if((b&1)!=0)
r = (r*a)%m;
a = (a*a)%m;
b/=2;
}
return (r*a)%m;
}
この問題に関する数学モデルおよび関連アルゴリズムは,[数論]大数を解くモードa^b%Rで既に言及されており,詳細なアルゴリズム解析が行われている.一つだけ言及しなければならないのは、初心者が犯しやすい間違いであり、abの結果を直接求めて余剰を取ることであり、理論的には可能であるが、コンピュータによるデジタル処理方式の特殊性、特にC++言語自体は大数の演算をサポートせず、現在最大で処理できるデータは64ビット2進数(_int 64タイプ)である.入力制限を見ると、この処理範囲をはるかに超えているはずなので、モジュールの性質でしかこの問題を作ることができません.
もちろん,O(b)のアルゴリズムとO(log 2 b)の2つの時間的複雑度のアルゴリズムはもちろん考慮できるが,問題に限定されたbはそれほど大きくない.もちろんO(log 2 b)のアルゴリズムをもっと熟知することをお勧めします.
#include <iostream>
#include <fstream>
using namespace std;
// a b n ( a^b %n )
// a b ， ，
//
int modExp( int a, int b, int r )
{
int Result=1;
while( b!=0 )
{
if ( b%2==1 )
Result = Result*a %r;
a = a * a % r;
b = b / 2;
}
return Result;
}
int main()
{
ifstream inData("SECRET.DAT", ios::in);
ofstream outData("SECRET.OUT", ios::out);
int a,b,c;
inData>>a>>b>>c;
outData<<modExp(a,b,c);
return 0;
}