一个很简单的ACM题,这个提交后怎么会“Time Limit Exceed”?Description 给你一个整数m(1《m《1000000),你能快速算出m的因子个数是个数n吗?一个整数本身是自己的因子!Input 输入数据包含多个测试实
来源:学生作业帮助网 编辑:作业帮 时间:2024/11/05 19:33:37
一个很简单的ACM题,这个提交后怎么会“Time Limit Exceed”?Description 给你一个整数m(1《m《1000000),你能快速算出m的因子个数是个数n吗?一个整数本身是自己的因子!Input 输入数据包含多个测试实
一个很简单的ACM题,这个提交后怎么会“Time Limit Exceed”?
Description
给你一个整数m(1《m《1000000),你能快速算出m的因子个数是个数n吗?一个整数本身是自己的因子!
Input
输入数据包含多个测试实例,每组数据占一行,每行为一个整数m(如上定义).
Output
对于每个测试实例,输出相应的结果.每个结果占一行.
Sample Input
1
5
10
20
Sample Output
1
2
4
6
代码:
#include"stdio.h"
int main()
{
\x05long n,m,i;
\x05while(scanf("%ld",&n)!=EOF)
\x05{
\x05\x05m=0;
\x05\x05for(i=1;i
一个很简单的ACM题,这个提交后怎么会“Time Limit Exceed”?Description 给你一个整数m(1《m《1000000),你能快速算出m的因子个数是个数n吗?一个整数本身是自己的因子!Input 输入数据包含多个测试实
可能是测试数据太变态了,出题者故意用来卡这种算法的
我们可以这么做 假设 m = p1^a1 * p2^a2 *..pk^ak..
那么它因子的个数就是(a1+1)(a2+1)...(ak+1).因为对于每个pi来说,我们可以选择有ai+1种选择(包括不选,选1个,选2个...选ai个)
那么也就是说我们只要对m进行质因素分解就可以了,先打一个素数表prime[],
然后对m进行分解,比如说20 = 2^2 * 5^1,我们计算出 因子2的个数2,和因子5的个数1
那么答案就是(2+1)*(1+1)= 6