andyli

题解 UVA11879 【Multiple of 17】
题目:UVa11879 Multiple of 17题目大意:给出$N(1\leq N\leq 10^{100})...
扫描右侧二维码阅读全文
02
2018/11

题解 UVA11879 【Multiple of 17】

题目:UVa11879 Multiple of 17

题目大意:

给出$N(1\leq N\leq 10^{100})$,判断$N\ \text{mod}\ 17$的结果是不是$0$。是则输出$1$,不是则输出$0$。

输入格式:

输入包含多组数据,每组数据只有一行,为$N$。输入以$0$结束。

输出格式:

对于每组数据,输出$1$或$0$。


基础知识:

首先,我们要记住几个公式:
$$(a+b)\ \text{mod}\ n=((a\ \text{mod}\ n)+(b\ \text{mod}\ n))\ \text{mod}\ n$$
$$(a-b)\ \text{mod}\ n=((a\ \text{mod}\ n)-(b\ \text{mod}\ n) + n)\ \text{mod}\ n$$
$$ab\ \text{mod}\ n=(a\ \text{mod}\ n)(b\ \text{mod}\ n)\ \text{mod}\ n$$
注意在减法中,由于$a\ \text{mod}\ n$可能小于$b\ \text{mod}\ n$,需要在结果加上$n$,而在乘法中,需要注意$a\ \text{mod}\ n$和$b\ \text{mod}\ n$相乘是否会溢出。一般乘法要用long long保存中间结果,例如:

int mul_mod(int a, int b, int n){
    a %= n; b %= n;
    return int((long long)a * b % n);
}

问题求解:

现在我们回到问题上来。首先读入的是字符串,因为$10^{100}$太大了,long long都存不下。然后把大整数写成“自左向右”的形式:$1234=((1\times 10+2)\times 10+3)\times 10+4$,然后用前面的公式,每步取模。

代码:

#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 105;

char str[maxn];
int main()
{
    while ((~scanf("%s", str)) && str[0] != '0')
    {
        int len = strlen(str), ans = 0;
        for (int i = 0; i < len; i++)
            ans = int(((long long)ans * 10 + str[i] - '0') % 17);
        printf("%d\n", !ans);
    }
    return 0;
}

当然,也可以把ans声明成long long类型的。

Last modification:June 25th, 2019 at 11:10 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment