ブルーブリッジカップ歴代試験問題マトリクスコイン反転(大数)
2321 ワード
問題の説明
明ちゃんはまずコインをn行m列の行列に並べた.
その後、明ちゃんはコインごとにQ操作を行いました.
x行目y列目の硬貨をQ操作する定義:i*x行目、j*y列目の硬貨をすべて反転する.
ここでiとjは任意に操作を実行可能な正の整数であり、行番号と列番号はいずれも1から始まる.
明ちゃんがすべてのコインにQ操作をした後、彼は奇跡を発見しました.すべてのコインは正面を向いています.
明ちゃんは最初に何枚のコインが反対側に向いているか知りたいです.そこで、彼は親友のMさんに助けを求めた.
聡明なMさんは、すべてのコインをもう一度Q操作するだけで、最初の状態に戻ることができると明さんに言った.しかし、明ちゃんは怠け者で、そのようにしたくない.そこで明ちゃんはあなたが彼にもっと良い方法を与えることを望んでいます.彼に答えを計算してもらう.
入力フォーマット
入力データには1行、2つの正の整数n mが含まれており、意味はタイトルの説明を参照してください.
出力フォーマット
最初に何枚のコインが反対側に上向いたかを示す正の整数を出力します.
サンプル入力
2 3
サンプル出力
1
データ規模と約定
10%のデータに対して、n、m<=10^3;
20%のデータに対して、n、m<=10^7;
40%のデータに対して、n、m<=10^15;
100%のデータに対してn,m<=10^1000(10の1000乗).
【問題解きの考え方】
详细分析これは他の人の分析で、私は私のコードを记录して、私に分析してどうせ私は分析できない
明ちゃんはまずコインをn行m列の行列に並べた.
その後、明ちゃんはコインごとにQ操作を行いました.
x行目y列目の硬貨をQ操作する定義:i*x行目、j*y列目の硬貨をすべて反転する.
ここでiとjは任意に操作を実行可能な正の整数であり、行番号と列番号はいずれも1から始まる.
明ちゃんがすべてのコインにQ操作をした後、彼は奇跡を発見しました.すべてのコインは正面を向いています.
明ちゃんは最初に何枚のコインが反対側に向いているか知りたいです.そこで、彼は親友のMさんに助けを求めた.
聡明なMさんは、すべてのコインをもう一度Q操作するだけで、最初の状態に戻ることができると明さんに言った.しかし、明ちゃんは怠け者で、そのようにしたくない.そこで明ちゃんはあなたが彼にもっと良い方法を与えることを望んでいます.彼に答えを計算してもらう.
入力フォーマット
入力データには1行、2つの正の整数n mが含まれており、意味はタイトルの説明を参照してください.
出力フォーマット
最初に何枚のコインが反対側に上向いたかを示す正の整数を出力します.
サンプル入力
2 3
サンプル出力
1
データ規模と約定
10%のデータに対して、n、m<=10^3;
20%のデータに対して、n、m<=10^7;
40%のデータに対して、n、m<=10^15;
100%のデータに対してn,m<=10^1000(10の1000乗).
【問題解きの考え方】
详细分析これは他の人の分析で、私は私のコードを记录して、私に分析してどうせ私は分析できない
#include
#include
#include
using namespace std;
string mul(string str1,string str2) //
{
int len1 = str1.length();
int len2 = str2.length();
int num[1005];
string res="";
memset(num,0,sizeof(num));
int i,j;
for(i=len1-1;i>=0;i--)
{
for(j=len2-1;j>=0;j--) // str[i]*str[j] len1-1-i+len2-1-j 0
num[len1-1-i+len2-1-j] = num[len1-1-i+len2-1-j]+(str1[i]-'0')*(str2[j]-'0');
}
for(i=0;i=10)
{
num[i+1] = num[i+1]+num[i]/10;
num[i] = num[i]%10;
}
}
for(i=len1+len2-1;i>=0;i--) // 0
if(num[i] != 0)
break;
for(;i>=0;i--)
res += num[i]+'0';
return res;
}
int compare(string str1,string str2,int num) //
{
int len1 = str1.length();
int len2 = str2.length();
// cout< len2+num)
return 1;
else if(len1 < len2+num)
return -1;
else //len1 == len2+num
{
for(int i=0;i str2[i])
{
return 1;
}
else if(str1[i] < str2[i])
{
return -1;
}
}
}
return 1;
}
string root(string str) //
{
int len = str.length();
string res="";
int num,i,j,flag;
if(len%2==0)
num = len/2-1;
else
num = len/2;
for(i=0;i>str1>>str2;
string res;
str1 = root(str1);
str2 = root(str2);
res = mul(str1,str2);
cout<