題目描述：
/**
牛牛以前在老師那里得到了一個(gè)正整數(shù)數(shù)對(duì)(x, y), 牛牛忘記他們具體是多少了。
但是牛牛記得老師告訴過(guò)他x和y均不大于n, 并且x除以y的余數(shù)大于等于k苍在。
牛牛希望你能幫他計(jì)算一共有多少個(gè)可能的數(shù)對(duì)绝页。
輸入描述:
輸入包括兩個(gè)正整數(shù)n,k(1 <= n <= 10^5, 0 <= k <= n - 1)荠商。
輸出描述:
對(duì)于每個(gè)測(cè)試用例, 輸出一個(gè)正整數(shù)表示可能的數(shù)對(duì)數(shù)量。
輸入例子1:
5 2
輸出例子1:
7
例子說(shuō)明1:
滿足條件的數(shù)對(duì)有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)
*/
思路如下：
暴力枚舉
枚舉y抒寂，若y<=K那么不存在這樣的數(shù)對(duì)
y>K時(shí), y 2y 3y ... ty ty<=N都是產(chǎn)生相同的對(duì)
y 2y 3y ... ty ty<=N都是產(chǎn)生x 相應(yīng)為{y+K, y+K+1, y+y-1}, {2y+K, ... 2y+y-1},.....
K, K+1,...y-1這么多種余數(shù)
N可以產(chǎn)生多少個(gè)就看具體y
代碼如下：
#include<stdio.h>
#include<iostream>
typedef long long LL;
using namespace std;
int main(){
int N, K;
LL res=0;
scanf("%d%d", &N, &K);
if(K==0){
res=(LL)N*N;
}
else{
//枚舉y结啼，若y<=K那么不存在這樣的數(shù)對(duì)
//y>K時(shí), y 2y 3y ... ty ty<=N都是產(chǎn)生相同的對(duì)
for(int y=K+1; y<=N; y++){
//y 2y 3y ... ty ty<=N都是產(chǎn)生x 相應(yīng)為{y+K, y+K+1, y+y-1}, {2y+K, ... 2y+y-1},.....
//K, K+1,...y-1這么多種余數(shù)
//N可以產(chǎn)生多少個(gè)就看具體y
res+=(N/y)*((y-1)-K+1);
//N可以產(chǎn)生余數(shù)
res+=max(0, N%y-K+1);
}
}
printf("%lld", res);
return 0;
}
