大きい整数の型を取る少しの理解
2248 ワード
大整数型取りの基本原理はxに基づいて10の少なくとも1回の方に乗っても、最終的に得られた型の結果は同じです(これは私を長い間引っ張っていました...)
テスト:
1.型取りの一般的な公式:
一.(a+b)mod n = ((a mod n)+(b mod n) mod n
二.(a-b)mod n = ((a mod n)-(b mod n)+n) mod n
三.ab mod n = (a mod n)(b mod n) mod n
例えば、2つの整数の積を求めるモードは、積がINT_を超える可能性があるためMAXなのでlong longで中間値を格納すべきです.
2.適用:大整数型取り
構想:まず、大きい整数をこの形式に分解する:1234=(((1*10+2)*10+3)*10+4
この形式は我々の前の型取り式を適用し,段階的に型を取ることができることが容易に分かった.
型取りコード:
テスト:
#include
#include
char a[10000 + 10];
int main()
{
int l, len;
// while(~scanf("%s%d", a, &b)){
// len = strlen(a);
// int ans = 0;
// for(int i = 0; i < len; i++)
// {
// ans = (int)(((long long) ans*10 + a[i] - '0') % b);
// printf ("%d ", ans);
// }
// //long long
// printf("%d
", ans);
// }
// return 0;
scanf("%d%d",&l,&len);
printf("%d%d%d%d",(l*10)%len,(l*100)%len,(l*1000)%len,(l*10000)%len);
}
1.型取りの一般的な公式:
一.(a+b)mod n = ((a mod n)+(b mod n) mod n
二.(a-b)mod n = ((a mod n)-(b mod n)+n) mod n
三.ab mod n = (a mod n)(b mod n) mod n
例えば、2つの整数の積を求めるモードは、積がINT_を超える可能性があるためMAXなのでlong longで中間値を格納すべきです.
int mul_mod(int a, int b, int n)
{
a %= n;
b %= n;
return (int) ((long long)a*b % n);
}
2.適用:大整数型取り
構想:まず、大きい整数をこの形式に分解する:1234=(((1*10+2)*10+3)*10+4
この形式は我々の前の型取り式を適用し,段階的に型を取ることができることが容易に分かった.
型取りコード:
#include
#include
char a[10000 + 10];
int main()
{
int l, len;
while(~scanf("%s%d", a, &b)){
len = strlen(a);
int ans = 0;
for(int i = 0; i < len; i++)
{
ans = (int)(((long long) ans*10 + a[i] - '0') % b);
printf ("%d ", ans);
}
//long long
printf("%d
", ans);
}
return 0;
// scanf("%d%d",&l,&len);
// printf("%d%d%d%d",(l*10)%len,(l*100)%len,(l*1000)%len,(l*10000)%len);
}