列表

详情


WY49. 数对

描述

牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。

但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。

牛牛希望你能帮他计算一共有多少个可能的数对。

输入描述

输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。

输出描述

对于每个测试用例, 输出一个正整数表示可能的数对数量。

示例1

输入:

5 2

输出:

7

说明:

满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 296KB, 提交时间: 2020-02-01

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    int ret=n-k;
    unsigned long long count=0;
    if(k==0)
        count=(long long)n*n;
    else{
        for(int i=1;i<=ret;i++){
            count+=i;
            int j=n%(i+k)-k+1;
            int z=(n/(i+k)-1)*i;
            if(j>=0)
                count=count+j+z;
            else
                count=count+z;
        }
    }
    printf("%llu\n",count);
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 320KB, 提交时间: 2022-01-25

#include<stdio.h>
int main()
{
   int n,k;
    scanf("%d%d",&n,&k);
    if(k==0)
    {
         printf("%lld",(long long )n*n);
        return 0;
    }
    long long c=0;
    for(int y=k+1;y<=n;y++)
    {
          int remain=n%y-(k-1);
        if(remain<0)  remain=0;
        c+=remain+(y-k)*(n/y);
    }
    printf("%lld",c);
   return 0;
}

上一题