文远知行杯E题枚举求和题解

题面

https://ac.nowcoder.com/acm/contest/9692/E

解题

首先研究 k|gcd(i, j) . 很显然, 如果该式成立, 那么 k 必然是 i, j 的公因子, 也就是说 i, j 都是 k 的倍数. 所以我们所求的就是符合要求的数对的个数, 根据数学知识 1 ~ n 中有 a = n / k 个 k 的倍数, 1 ~ m 中有 b = m / k 个 k 的倍数, 符合要求的数对个数就是 a * b .

踩的坑

别问, 问就是不开long long见祖宗.

完整AC代码

点我查看完整代码

#include<cstdio>

typedef long long ll;

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        ll ans = (ll)(n / k) * (m / k);
        printf("%lld\n", ans);
    }
    return 0;
}