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

這其實是一道數學題，核心代碼為

下面先上正确代碼，證明過程暫時不會，還望各位路過大佬不吝賜教。

1 #include <iostream>
 2 using namespace std;
 3 
 4 //傳回x和y的最大公約數
 5 long long gcd(long long x, long long y)
 6 {
 7     long long z = y;
 8     while(x%y!=0)
 9     {
10         z = x%y;
11         x = y;
12         y = z;
13     }
14     return z;
15 }
16 
17 int main()
18 {
19     int T;
20     cin>>T;
21     while(T--)
22     {
23         long long a,b,c,k;
24         cin>>a>>b>>c>>k;
25         if(c%gcd(b,gcd(a,k-1))==0)
26             cout<<"Yes"<<endl;
27         else
28             cout<<"No"<<endl;
29     }
30     return 0;
31 }      

 這題挺有意思。。。證明過程會及時補充。

 特意備注：擴充歐幾裡得

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

『注:本文來自部落格園“小溪的部落格”，若非聲明均為原創内容，請勿用于商業用途，轉載請注明出處http://www.cnblogs.com/xiaoxi666/』