正整数对(x,y),x,y都小于等于n,x/y的余数大于等于k,输入为n,k,输出有多少个,比如输入5 2,输出为7, 对数分别为(2,3)(2,4)(2,5)(3,4)(3,5)(4,5)(5,3),代码如下:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
System.out.println(searchCount(n, k));
}
public static int searchCount(int n, int k) {
int count = 0; //记录找到的整数对个数
int temp;
//思路:固定y,找x
for (int y = k + 1; y <= n; y++) { // x%y>=k,说明y>k
// 假设n = a*y +b;在每个长度为y的区间里只有(y-k)个数模y余数>=k。
count += n/y*(y-k);
temp = n%y;
if(temp >= k) { //再考虑余数b是否>=k
count += temp-k+1;
}
}
return count;
}
}
为什么x%y>=k,就能推断出说明y>k?count += n/y*(y-k)和count += temp-k+1这两句结合为什么就能够求出最终个数?
x%y>=k
的意思是x除以y的余数大于等于k,余数肯定是小于y的,因此y肯定大于k。count += n/y*(y-k)
的意思就是那句注释:count += temp-k+1;
是计算n = a*y +b
中的b里面还有多少个满足条件的数对。举个例子,n=18,k=3。
首先,y肯定是大于3的,因为3以内的除数余数不可能大于等于3。所以for循环是从
k+1
开始的。对于任何一个y,例如7,首先把n=18写成
18 = 2 * 7 + 4
的形式,也就是把1~18这段范围内的整数分成了1~7、8~14、15~18这三段。前两段里面每段都有y-k=4
个数满足余数大于等于3的要求。而最后一段里面只有b-k+1=2
个数满足,也就是17、18
这两个数。建议你在数轴上画一下,应该就能明白了。