SCP-J T1,#4-5和9-10 TLE,#6-7 RE,40分求助

学术版

Karl_Wan @ 2024-10-13 12:41:25

SCP-J T1 题目传送门

评测状态:1-3 AC,4-5 TLE,6-7 RE,8 AC,9-10 TLE(R181736363)

思路:若 n \div x = k \cdots \cdots r(其中 x 为除数),那么直接用 n \div k 可以反推出除数 x(忽略余数部分)。然后再把除数 x 向下枚举,如果 n \div x 还是等于 k,那么 ans \gets ans+1 并且 x \gets x-1;否则就跳出循环。

代码:

#include <iostream>
using namespace std;
long long n,beichushu,shang;
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>beichushu>>shang;
        if(shang==0)//特判,如果商等于0,那么除数一定大于被除数了,这样情况下余数只有一种可能,那就是等于被除数,所以是1
        {
            cout<<1<<'\n';
            continue;
        }
        long long u=beichushu/shang;
        long long i=u;
        long long ans=0;
        while(1)
        {
            if(beichushu/i!=shang) break;
            //cout<<i<<endl;
            ans++;i--;
        }
        cout<<ans<<'\n';
    }

    return 0;
}

请讲讲我的算法有什么错误,或者程序实现细节有哪一点不对,然后再给出代码。谢谢!

感谢各位dalao的帮助!


by zhouyixuan11 @ 2024-10-13 12:47:07

T了,数学算吧

long long t1=n/(k+1)+1,t2=n/k; 
cout<<t2-t1+1<<endl;

by __galaxy_1202__ @ 2024-10-13 12:47:20

@KarlWan 复杂度不对,太慢了


by __galaxy_1202__ @ 2024-10-13 12:47:41

@KarlWan 这是数学题,推个公式吧


by Karl_Wan @ 2024-10-13 13:01:48

@zhouyixuan11 请解释一下这个公式,谢谢!


by Karl_Wan @ 2024-10-13 13:52:41

@20121202Tzy


by __galaxy_1202__ @ 2024-10-13 14:04:25

@KarlWan n/k表示商是k的最大除数,n(k+1)+1表示商是k的最小除数,而不同的除数除出来的的余数自然不同,所以相减即可


by Karl_Wan @ 2024-10-13 15:04:27

谢谢! @20121202Tzy


|