美团codeM预赛B 模

2019-04-14 16:09发布

站内文章 / 模拟电子
16574 0 1406
 模 时间限制：1秒 空间限制：32768K 给定四个正整数a,b,c,k，回答是否存在一个正整数n，使得a*n在k进制表示下的各位的数值之和模b为c。 
输入描述:
第一行一个整数T(T <= 5,000)。 接下来T行，每行四个正整数a,b,c,k（1 ≤ a ≤ 10^18; 2 ≤ k ≤ 10^18; 0 ≤ c < b ≤ 10^18）表示一个询问，所有输入都是十进制的。

输出描述:
对于每组数据输出一行，Yes表示存在，No表示不存在。
输入例子1:
2 3 9 5 10 7 3 1 10
输出例子1:
No Yes 解题思路：设a转化为k进制后，各位和为sum，扩大x倍后，若没有进位的话变为sum*x，而一次进位对和的贡献为（1-k），所以(x*sum+y*(1-k)))%b=c，即x*sum+y*(1-k)=z*b+c，移项后变为x*sum+y*(k-1)+z*b=c，根据拓展欧几里得定理，c%gcd(b,gcd(sum,k-1))==0
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long const int INF = 0x3f3f3f3f; LL gcd(LL a,LL b) { return b?gcd(b,a%b):a; } int main() { int t; LL a,b,c,k; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld%lld",&a,&b,&c,&k); LL sum=0; while(a) {sum+=a%k;a/=k;} if(c%gcd(b,gcd(sum,k-1))==0) printf("Yes "); else printf("No "); } return 0; }

热门文章