HDOJ 5373 The shortest problem 【数论】

HDOJ 5373 The shortest problem 【数论】

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5373

---

题目给一个初始数据和重复次数
每一次都在初始数据末端连接上现有数据的各个位的和
之后对最后得出的数据除以11，如果可以整除输出Yes，否则输出No

---

可以被11整除的数有一个特征：
奇数位减去偶数位的数最后得出的数如果能被11整除，原数就可以被11整除，否则原数也不能被11整除
因此用sum保存之前的各个位之和，
遍历t次之后将dif与11取模即可
注意使用之前的位数为奇数或偶数，现在的位数为奇数或偶数来判断对最末尾的数是先加还是先减

---

提供队友的法二：
以358÷11为例：

所以对于每次得出的结果直接对11取模即可。。。不过还是要保存原先的每位的和
保证下次加入末尾的数据依然正确
就素酱紫。。。

---

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<set> using namespace std; #define clr(c) memset(c, 0, sizeof(c)); const int INF = 0x3f3f3f3f; typedef long long LL; int n, t, Case; int dif, len; int sum; int flag, num; int oddBefore, odd; int ll; void fun(int nn){int ll = 0;int difsub = 0;int difplus = 0;flag = 1;while(nn){num = nn % 10;difplus += flag*num;difsub += -1*flag*num;flag *= -1;sum += num;nn /= 10;ll++;}if(ll & 1) odd = true;else odd = false;if(odd == oddBefore){dif += difsub;oddBefore = false;}else{dif += difplus;oddBefore = true;} }int main(){Case = 1;while(~scanf("%d%d", &n, &t)){if(n == -1 && t == -1) break;printf("Case #%d: ", Case++);if(n == 0){puts("Yes");continue;}if(t == 0){if(n % 11) puts("No");else puts("Yes");continue;}flag = 1, num = 0, dif = 0, sum = 0, ll = 0;int tempN = n;int difplus = 0;int difsub = 0;while(tempN){num = tempN % 10;difplus += flag*num;difsub += -1*flag*num;flag *= -1;sum += num;tempN /= 10;ll++;}if(ll & 1){oddBefore = true;dif = difplus;}else{oddBefore = false;dif = difsub;}for(int i = 0; i < t; i++) fun(sum);if(dif % 11) puts("No");else puts("Yes");}return 0; }

版权声明：本文为博主原创文章，未经博主允许不得转载。

转载于:https://www.cnblogs.com/miaowTracy/p/4836758.html

总结

以上是生活随笔为你收集整理的HDOJ 5373 The shortest problem 【数论】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。