使用**裴蜀定理**优化
#include<stdio.h>
long long gcd(long long a, long long b) {
	if (a % b == 0) {
		return b;
	}
	return gcd(b, a % b);
}
int main() {
	int n;
	scanf("%d", &n);
	long long a, b, c;
	while (n--) {
		scanf("%lld%lld%lld", &a, &b, &c);
		int t = gcd(a, b);
		if (c % t == 0) {
			printf("Yes\n");
		}
		else {
			printf("No\n");
		}
	}
}

👍 👍

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b,n;
        scanf("%d%d%d",&a,&b,&n);
        int t;
        while(t=a%b){
           a=b;
           b=t; 
        }
        if(n%b==0){
            printf("Yes");
        }
        else{
            printf("No");
        }
        printf("\n");
    }
    return 0;
}

裴蜀定理：对于整数a, b，存在整数x, y使得 ax + by = gcd(a,b)

推论：方程 ax + by = c 有整数解 ⇔ gcd(a,b) 整除 c🎉️