题解：AT_diverta2019_d DivRem Number

题目(洛谷)
题目(AtCoder)
题目(Vjudge)

题意

给定一个 $N$，求所有的 $M$ 满足 $\lfloor \frac{N}{M}\rfloor = N \bmod M$。

分析

众所周知，除法的一般形式都是这样的：

$$N \div M = Q \cdots R$$

放入题中式子可得

$$N \div M = M \cdots M$$

$$\therefore N = M\times M + M$$

所以时间复杂度在 $O(\sqrt N)$ 左右，枚举 $M$ 能够通过。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i*i+i<=n;i++){
        if(n%i==0){
            ans+=(n/i)-1;
        }
    }
    cout<<ans;
    return 0;
}

TIPS

使用

#define int long long

可将整个程序所有的 int 变为 long long，可是这样做有一个弊端，就是 main() 的返回值会变成 long long，可是 C++ 中不允许这么做。

为了解决这个问题，我们可以将 main() 的返回值变为 signed（即无符号整数）也可以正常编译。