给定正整数 n 和 k，有互质的整数 a、b 满足： 2 <= a < b <= n b = a + m * k, m为正整数 求 a 和 b 所有可能的数量有多少

Question

用gcd求互质数的组，然后再用for循环赋值ab，和用for循环赋值m，以筛选出符合公式的内容，但是在oj上面一直超时，有大佬帮我改改嘛，孩子刚学c++，实在不会

#include
#include

using namespace std;

int gcd(int a,int b)
{
if (b == 0) return a;
return gcd(b, a % b);

}
int solve(int n, int k) {

int a = 2, b, j = 0;
for (b = a + 1; b <= n; b++) {
    for (a = 2; a <b; a++) {

        if (gcd(a, b) == 1) {  //利用判断两数的最大公约数是否互质数 
            for (int m = 1; m < b; m++) {
                if ((a + m * k) == b) {  //是否符合此式子 

                    j++;
                    break;
                }
            }
        }
    }
}

return j;

}
int main()
{
int n, k;
cin >> n >> k;

cout << solve(n, k)<< endl;
system("pause");
return 0;
}

Answer 1

穷举法双循环遍历就好了。用两个循环变量，判断是否互质，如果互质再判断是否满足b=a+m*k这个计算公式就行了