牛客练习赛25 A题 因子个数和
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
q次询问，每次给一个x，问1到x的因数个数的和。
输入描述:
第一行一个正整数q ； 接下来q行，每行一个正整数 x
输出描述:
共q行，每行一个正整数表示答案
示例1
输入
4 1 2 3 10
输出
1 3 5 27
说明
1的因数有1 2的因数有1,2 3的因数有1,3 以此类推
备注:
1<=q<=10 ,1<= x<=109
题意：输入一个n,求1~n的每个数因子的个数和，枚举1<=i<=sqrt(n)，n/i表示i作为因子出现的总次数，这样求大大的降低时间复杂度，所以可以得到一个函数关系式y=n/x，(x=1,2,3......)，也就是求函数y的离散值，则求出该函数与y轴，x轴围成的面积，又因为该函数关于点((sqrt(n),sqrt(n))对称，所以只要枚举i<=i<=sqrt(n)即可，求出的和乘以2,然后再减去sqrt(n)的平方就是结果了
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
long long int t,n;
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
long long int num=sqrt(double(n)),flag=0;
for(int i=1; i<=num; i++)
flag+=n/i;
flag*=2;
flag-=num*num;
printf("%lld\n",num);
}
return 0;
}
查看18道真题和解析