美团codeM预赛B 模

 模

时间限制：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 <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <stack> #include <cmath> #include <map> #include <bitset> #include <set> #include <vector> #include <functional> 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\n"); else printf("No\n"); } return 0; }