代码超时，求一个优化的思路。。。

Question

如果从整数区间[1,a]内取一个整数x, 从整数区间[1,b]内取一个整数y, 要求x和y的最大公约数为k.
问满足要求的（x,y）有多少对。规定（x,y）和（y,x）不重复计数。

例如分别从[1,3]和[1,5]区间取x和y, 则最大公约数为1的对为：
（1,1），（1,2），（1,3），（1,4），（1,5），（2,3），（2,5），（3,4），（3,5）
共9对
输入描述

输入3个整数a,b,k

输出描述

满足要求的（x,y）对的数目

输入样例

3 5 1

输出样例

9

#include<stdio.h>

int gcd(int m, int n) {
    int r = 0;
    while (n) {
        r = m % n;
        m = n;
        n = r;
    }
    return m;
}

int main() {
    int a;
    int b;
    int k;
    scanf_s("%d%d%d", &a, &b, &k);
    int count = 0;
    for (int i = 1; i <= (a<b ? a : b); i++) {
        for (int j = i; j <= (a>b ? a : b); j++) {
            if (gcd(i, j) == k) {
                count++;
            }
        }
    }
    printf("%d", count);
}

上面是我的代码，但是会超时...没什么好的思路，求指点

Answer 1

1.求最大公约数用辗转相减 2.在for循环中加入一条if(i%k==0&&j%k==0) 3.i从k开始循环