大きい整数の型を取る少しの理解

2248 ワード

大整数型取りの基本原理はxに基づいて10の少なくとも1回の方に乗っても、最終的に得られた型の結果は同じです(これは私を長い間引っ張っていました...)
テスト:
#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); }