标题:一道acm的题,提交TE,求大侠讲解一下解题思路(已附上自己思路和代码)
取消只看楼主
justNPC
Rank: 5Rank: 5
等 级:职业侠客
帖 子:101
专家分:311
注 册:2012-8-11
结帖率:100%
已结贴  问题点数:20 回复次数:7 
一道acm的题,提交TE,求大侠讲解一下解题思路(已附上自己思路和代码)
玩了一段魔兽争霸后,ZLP发现,出兵才是魔兽争霸中的王道!可是做为一名Acmer, ZLP发现这样一个道理,双方部队数量的 因子的个数相等时,部队的战斗力是相等的且等于他们因子的个数。例如双方的部队数量为6 和 8 时,因为6有四个因子(1  2  3  6 ) 而8(1 2 4 8) 也有四个因子,所以他们的战斗力都是4,所以他们的战斗力是相同的。这时候zlp想知道战斗力为n时,最小的部队数是多少?
Input
输入有多组数据,以EOF结束。
每组数据有一个数n,表示战斗力(即因子的个数)(1<=n<=1000)
Output
对于每组输入输出一个数m表示最小的部队数,数据保证1<=m<=10^18
Sample Input
1
4
6
Sample Output
1
6
12

这是我的代码 但是提交时老是TE
求大神讲解一下其他解题思路
http://acm.xidian. 这是原题的地址
程序代码:
#include<stdio.h>
#include<math.h>
int main()
{
    int yinzi(long int i);
    long int i,j,n,time,t,k;
    scanf("%d",&n);
    while(n!=EOF)
    {
        if(n==1)
            printf("%d\n",n);
        else if(n%2==1)                   //奇数的话 ,n必然是某个数的平方
        {    
            k=2;
            while(i<10e18)
            {
                i=k*k;
                time=yinzi(i);
                k++;
                if(n==time) break;
            }
            printf("%ld\n",i);
        }
        else                          //偶数的话,n必然是2的倍数
        {    k=1;
            while(i<10e18)
            {
                i=k*2;
                time=yinzi(i);
                k++;
                if(n==time) break;
            }
            printf("%ld\n",i);
        }
    scanf("%d",&n);        
    }
    return 0;
}
int yinzi(long int i)             //用于求解因子个数
{
    long int time,t,j;
    time=0;
    t=sqrt(i)+1;         //用于减少判断因子的次数
    for(j=1;j<t;j++)
    {
        if(i%j==0) 
        {
            if(i/j==j)
                time++;
            else
                time+=2;
        }
    }
    return time;
}
搜索更多相关主题的帖子: 魔兽争霸 战斗力 
2012-08-25 23:12
justNPC
Rank: 5Rank: 5
等 级:职业侠客
帖 子:101
专家分:311
注 册:2012-8-11
得分:0 
回复 2楼 demonleer
war3 超级经典 很多人都玩过
就是这题感觉坑爹啊 感觉按照我的思路做太耗费时间了

[ 本帖最后由 justNPC 于 2012-8-26 09:16 编辑 ]
2012-08-26 09:13
justNPC
Rank: 5Rank: 5
等 级:职业侠客
帖 子:101
专家分:311
注 册:2012-8-11
得分:0 
回复 5楼 xlj3105098
没注意i,但是这个程序是能运行,也能得出结果,就是没有在规定时间内解决问题,这应该是算法上的问题
2012-08-28 17:46
justNPC
Rank: 5Rank: 5
等 级:职业侠客
帖 子:101
专家分:311
注 册:2012-8-11
得分:0 
回复 6楼 a745043791
测试了几组数据好像不太对啊
比如说输入4的 时候 理论应该输出6的 你的却输出了15
2012-08-28 18:03
justNPC
Rank: 5Rank: 5
等 级:职业侠客
帖 子:101
专家分:311
注 册:2012-8-11
得分:0 
回复 9楼 a745043791
程序里面错误
for(int o=0;o<=i;o++)  

这个不能在里面定义 o
改成
int 0for(o=0;o<=i;o++)
就行了
还有
printf("%d",out);
这个括号是汉语输入时的括号
测试了一下 若要求的n是奇数个的话 能输出正确答案,偶数的话就不对,你能把算法的思路说一下么,有点看不懂啊

我发现若输入n是奇数的话,所要求结果正好等于2^(n-1)
2012-08-28 19:41
justNPC
Rank: 5Rank: 5
等 级:职业侠客
帖 子:101
专家分:311
注 册:2012-8-11
得分:0 
的确按照杨大哥的思路下去却实能简便很多
可以把输入的n拆分成几个最简质因数相乘的形式 比如24=2*2*2*3
但是如何组合几个 因数 但是直接用这几个数能组合出来的最小数是   2^2*3*5*7=420
          然而    把因子中得2*2组合成4的话      2^3*3^2*5=360
如果一个数很大能拆分成很多个质因数 而且其中2,3的数量比较多的话 组合的数量就会更多
这个问题 今天想了一天 也没想出什么方法去处理
2012-08-29 22:15
justNPC
Rank: 5Rank: 5
等 级:职业侠客
帖 子:101
专家分:311
注 册:2012-8-11
得分:0 
求杨大哥代码一阅,关于怎样组合因数,求得最小值这一步的处理没啥头绪啊
2012-08-30 21:43
justNPC
Rank: 5Rank: 5
等 级:职业侠客
帖 子:101
专家分:311
注 册:2012-8-11
得分:0 
回复 32楼 zhu224039
确实挺纠结的
2012-09-01 09:40



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-380118-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.160867 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved