codeM美团编程大赛初赛B轮D题

[编程题] 模

时间限制：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表示不存在。

输入例子:
2
3 9 5 10
7 3 1 10

输出例子:
No
Yes

这其实是一道数学题，核心代码为

下面先上正确代码，证明过程暂时不会，还望各位路过大佬不吝赐教。

 #include <iostream>

 using namespace std;

 //返回x和y的最大公约数

 long long gcd(long long x, long long y)

 {

     long long z = y;

     while(x%y!=)

     {

         z = x%y;

         x = y;

         y = z;

     }

     return z;

 }

 int main()

 {

     int T;

     cin>>T;

     while(T--)

     {

         long long a,b,c,k;

         cin>>a>>b>>c>>k;

         if(c%gcd(b,gcd(a,k-))==)

             cout<<"Yes"<<endl;

         else

             cout<<"No"<<endl;

     }

     return ;

 }

这题挺有意思。。。证明过程会及时补充。

特意备注：扩展欧几里得

巴特西

codeM美团编程大赛初赛B轮D题

20170627更新，以下是walker大佬的解答

最新文章

热门文章