1214 - Large Division -- LightOj（大数取余）

http://lightoj.com/volume_showproblem.php?problem=1214

这就是一道简单的大数取余。

还想还用到了同余定理：

所谓的同余，顾名思义，就是许多的数被一个数d去除，有相同的余数。d数学上的称谓为模。如a=6,b=1,d=5,则我们说a和b是模d同余的。因为他们都有相同的余数1。

////

数学上的记法为：

a≡ b(mod d)

可以看出当n<d的时候,所有的n都对d同商,比如时钟上的小时数,都小于12,所以小时数都是模12的同商.

对于同余有三种说法都是等价的,分别为:

(1) a和b是模d同余的.

(2) 存在某个整数n,使得a=b+nd .

(3) d整除a-b.

可以通过换算得出上面三个说法都是正确而且是等价的.

 

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<algorithm>

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

#define N 100000

#define ESP 1e-8

#define INF 0x3f3f3f3f

#define memset(a,b) memset(a,b,sizeof(a))

int main()

{

    int T, t=;

    scanf("%d", &T);

    while(T --)

    {

        char s[];

        LL b;

        scanf("%s %lld", s, &b);

        if(b < )

            b = -b;

        printf("Case %d: ", t++);

        int len = strlen(s);

        if(len ==  && s[] == '')

        {

            printf("divisible\n");

            continue;

        }

        LL sum = ;

        for(int i=; i<len; i++)

        {

            if(s[i] == '-')

                continue;

            sum = sum* + s[i]-'';

            sum = sum%b;

        }

        if(sum == )

            printf("divisible\n");

        else

            printf("not divisible\n");

    }

    return ;

}