C++有多少个不同的n/i

给定一个n。对于i从1到n。找出有多少个不同的n/i
如：n=6
有4个不同的n/i：6 3 2 1
输入
第一行一个T。 表示有T组数据(T < 100000)
之后T行。 每行一个n(n <= 10^18)
输出
每行输出一个数 表示不同的个数
样例输入
3
6
8
10
样例输出
4
4
5
提示
对于50%的数据：n <= 100000 T <= 10
对于100%的数据：n <= 10^18 T < 100000

引用chatgpt部分指引作答：
运行结果：

img

这道题目可以用数学方法解决。假设当前要求的是 $n/i$，那么根据除法的性质，$n/i$ 可以写成 $n/(n/j)$ 的形式，其中 $j$ 是 $i$ 的约数。因此，问题就转化为了求 $n$ 的所有约数 $j$，然后计算 $n/j$ 的不同值的个数。

计算 $n$ 的约数可以采用试除法，枚举 $[1, \sqrt{n}]$ 之间的数，如果可以整除 $n$，那么 $n$ 就有两个约数，分别是这个数和 $n$ 除以这个数得到的商。需要注意的是，如果 $i = \sqrt{n}$，则只需要计算一次，因为 $i$ 只会被计算一次，而 $n/i$ 的值也只会被计算一次。

对于每个 $n$，可以先预处理出其所有约数，然后再遍历一遍计算不同的 $n/j$ 的个数即可。时间复杂度为 $O(T \sqrt{n} \log n)$。

#include <iostream>
#include <set>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        set<long long> s;
        for (long long i = 1; i <= n; i++) {
            s.insert(n / i);
        }
        cout << s.size() << endl;
    }
    system("pause");
    return 0;
}

从每个整数向1逐个进行整除结果判断，如果与当前个结果相同，则继续循环；如果不相同，则新的结果记录为当前结果，计数加1
当前结果默认为1，因为整数除以自身肯定是1，后续的整除结果必然是递增关系


#include <iostream>
using namespace std;
int main()
{
    int n,k,count = 0;
    long long m;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
          cin>>m;
          count = 1;
          k = 1;
          for(int j=m-1;j>=1;j--)
          {
              if(m/j != k)
              {
                  k++;
                  count++;
              }
          }
          cout<<k<<endl;
    }
}

引用chatGPT作答，
解题思路：

首先我们可以通过枚举n的因子i，然后计算n/i来判断是否与之前出现过相同的数，如果不同，则计数器加1。但是，这种算法复杂度为O(n)，不适用于n比较大的情况。

因此，我们需要寻找一种更快的算法。我们可以把n/i看作是一组商和余数的形式，即n/i和n%i。可以发现，当i变化时，商n/i是单调递减的，而余数n%i是单调递增的。因此，我们可以用两个指针分别指向商和余数，然后从大到小枚举商，从小到大枚举余数。每当遇到不同的商或余数时，就将计数器加1。

时间复杂度为O(sqrt(n))。
解题代码：

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        unordered_set<long long> nums;  // 用unordered_set存储不同的n/i
        for (long long i = 1; i * i <= n; i++) {  // 枚举商
            nums.insert(n / i);  // 插入商
            nums.insert(n / (n / i));  // 插入商的相反数
        }
        cout << nums.size() << endl;  // 输出不同的n/i的数量
    }
    return 0;
}

其中unordered_set是C++ STL中的容器，用于存储不重复的元素，查找、插入和删除的时间复杂度都是O(1)。在代码中，我们用unordered_set存储不同的n/i，最后输出它的大小就是不同的n/i的数量。