模

[编程题]模

热度指数：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

算法知识视频讲解

元气の悟空

#include<stdio.h>
int T;
long long gcd(long long x, long long y){
    return y?gcd(y,x%y):x;
}
int main(){
    for(scanf("%d",&T);T--;){
        long long a,b,c,k;
        scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
        if(c%gcd(b,gcd(a,k-1))==0) printf("Yes\n");
        else printf("No\n");
    }
}

发表于 2017-11-08 18:27:03 回复(0)