模

[编程题]模

热度指数：35 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定四个正整数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

输出

No
Yes

算法知识视频讲解

ZAFU_张烨浩

发表于 2020-09-28 20:12:58

先考虑本题的一个子问题如何表示一个数字x在k进制下的数位和？答案：x + （1 - k）* n (其中n为未知数)证明：对于一个数字来说，如果只有一位，那么在当前进制下他的数位和就是x，由于当数字大于等于k时会产生进位所以数位和会损失（k - 1），所以新的数位和一定可以表示成上述式子那么这个问展开全文