首页 > 代码库 > 余数之和sum

余数之和sum

2024-07-31 00:12:11   220人阅读

余数之和sum
Time Limit:5000MS Memory Limit:165888KB 64bit IO Format:%lld & %llu

SubmitStatus

Description

给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

输入仅一行，包含两个整数n, k。

Output

输出仅一行，即j(n, k)。

Sample Input

5 3

Sample Output

7

Hint

50%的数据满足：1<=n, k<=1000 100%的数据满足：1<=n ,k<=10^9

Source

CQOI2007

意解: 晕..........打表找规律,加暴力对拍,终于A了,打完表后会发现其实解的集合是分块的.并且是形成等差数列;
AC代码:
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long ll;

int main()
{
    ll n,m,ans1,ans2,len,now,L,R,t;
    while(~scanf("%lld %lld",&n,&m))
    {
        ans1 = ans2 = 0;
        t = 1;
        /*for(int i = 1; i <= n; i++)
            ans1 += m % i;*/
        if(n >= m)
            ans2 = (n - m) * m,n = m;
        /*for(int i = 1; i <= m; i++)
            cout<<i<<":"<<m % i<<endl;*/
        L = 0;
        now = m;
        while(true)
        {
            t++;
            R = m / t + 1;
            if(R > now) break;
            if(R > n)
            {
                now = m / t;
                L = m % now;
                continue;
            }
            len = now - R + 1;
            R = L + (len - 1) * (t - 1);
            if(now > n)
            {
                L = m % n;
                len = n - m / t;
            }
            ans2 += (R + L) * len / 2;
            now = m / t;
            if(!now) break;
            L = m % now;
        }
        for(int i = min(now,n); i >= 2; i--) //提前跳出来的数有可能大于n;
            ans2 += m % i;
        cout<<ans2<<endl;
    }
}


余数之和sum


联系
我们