【oj每周推荐】（算法）勇敢的（或许是不幸的）CSDNer
10位CSDNer乘坐热气球在太平洋上空旅行，他们打算开香槟庆祝一下这个伟大的时刻。然而很不幸，他们发现气球上破了一个洞，氢气不断外泄，气球开始下降，很快他们就会掉到海洋里成为鲨鱼的甜品。
但他们并没有就此完蛋，只要其中一位能够牺牲自己，跳出气球，就可以挽救其余人的生命。那问题就变成了，谁会愿意这么做呢？有一个公平的办法来解决这个问题。首先，把这十个人从0到9编上号，然后每个人先在纸上写上一个大于等于1小于等于10000的整数，把这10个人写的数字相乘，等到一个结果a，找出a的约数的个数b，则b的个位就是要牺牲自己的CSDNer的编号。把这位英雄找出来吧！！
输入：每行一个大于等于1小于等于10000的整数
输出：b的个位数
样例：
输入：
1
2
6
1
3
1
1
1
1
1
那么a=1*2*6*1*3*1*1*1*1*1=36
a的约数有：1，2，3，4，6，9，12，18，36总共9个
则b=9
那么b的个位也是9
输出：9
[解决办法]
乱写的
private void button3_Click(object sender, EventArgs e)
{
ushort[] _Value = new ushort[] { 1 ,2,6,1,3,1,1,1,1,1};
this.Text = GetDivisorofUint(_Value).ToString();
}
private int GetDivisorofUint(ushort[] p_ValueNumb)
{
ulong _Value = 1;
for (int i = 0; i != p_ValueNumb.Length; i++)
{
_Value = _Value * p_ValueNumb[i];
}
Hashtable _HashValue = new Hashtable();
ulong _Numb = 1;
while (true)
{
if (_HashValue[_Numb] == null)
{
if (_Value % _Numb == 0)
{
ulong _ValueNumb = _Value / _Numb;
if (_HashValue[_ValueNumb] == null) _HashValue.Add(_ValueNumb, null);
if (_ValueNumb == _Numb) break;
_HashValue.Add(_Numb, null);
}
}
_Numb++;
if (_Numb == _Value) break;
}
string _Count = _HashValue.Count.ToString();
return int.Parse(_Count[_Count.Length - 1].ToString()); }
[解决办法]
- C# code
using System.Collections.Generic;using System;namespace ConsoleApplication1{ class Program { static Dictionary<int, int> dItems = new Dictionary<int, int>(); //存放据有输入数的质因数 static void Main(string[] args) { int[] Input = new int[10]; //输入 int n, MaxInput = 0; //当前输入，最大输入 //读入输入 for (int i = 0; i < 10; i++) { while (!int.TryParse(Console.ReadLine(), out n) || n <= 0 || n > 10000) { Console.WriteLine("该输入无效，请重新输入(需要1-10000的整数)。"); } Input[i] = n; if (MaxInput < n) { MaxInput = n; } } //求所有程序中可能用到的质数 GetItem(MaxInput); //分解所有整数 for (int i = 0; i < 10; i++) { Split(Input[i]); } //计算约数个数 int Count = 1; foreach (int i in dItems.Values) { Count *= 1 + i; } Console.WriteLine("英雄编号是：" + Count % 10); Console.Read(); } //分解P，表示为 a1^b1+a2^b2+...的形式 private static void Split(int p) { if (p == 1) { return; } if (dItems.ContainsKey(p)) //p是质数 { dItems[p]++; return; } for (int i = 2; i <= p && p > 1; i++) //找P的质因数 { if (p % i == 0) { dItems[i]++; p /= i; i--; } } } static void GetItem(int Max) //筛选法求素数，网上抄了个c的改了下 { int[] sieve = new int[Max + 1]; //Max以内的数 //step 1: //初始化（sieve[i] = 0 表示不在筛中，即不是质数；1表示在筛中） for (int i = 2; i <= Max; i++) //从2开始，因为0和1不是质数 sieve[i] = 1; //step 2: //偶数(2的倍数)肯定不是质数，所以应该先筛除 for (int i = 2; i <= Max / 2; i++) sieve[i * 2] = 0; int p = 2; //第一个质数是2 //step 3:从sieve中删去P的倍数 while (p * p <= Max) { //选下一个p p = p + 1; while (sieve[p] == 0) p++; int t = p * p; int s = 2 * p; while (t <= Max) { sieve[t] = 0; //删除 t = t + s; } } //step 4: 输出结果 for (int i = 2; i <= Max; i++) { if (sieve[i] != 0) { dItems.Add(i, 0); } } } }}
[解决办法]
虽然我没试过，但我觉得只要大家都把数写大点，百分之九十九是0号牺牲
所以这个方案很不公正
[解决办法]
- C/C++ code
#include <iostream>using namespace std;int SelectPerson(int *P);int main(){ int p[10]; int target = 0; for(int i = 0; i < 10; i++) cin >> p[i]; target = SelectPerson(p); if(!target) cout << "Some error occured." << endl; else cout << "The person is " << target%10 << endl;}int SelectPerson(int *p){ int sum = 1; int index = 0; for(int i = 0; i < 10; i++){ sum *= p[i]; } for(int j = 2; j < sum/2; j++){ if(sum%j == 0){ index++; } } return index;}
[解决办法]
晕，一个笔误，想写大于等于的，忘了修改，版主帮忙删除上面的回复吧。
5楼给得很快，看起来也比较简单，就是一个循环，所以也最容易查错了（没别的意思）。
HashTable似乎没有List效率高，if (_HashValue[_ValueNumb] == null)这个判断多余了，因为添加的元素就是null，所以就算存在也是null，等号永远成立，不过后面的添加会报错，因为出现重复键了。
if (_Numb == _Value) break; 改为if (_Numb >= _ValueNumb ) break; 的话，效率会更高，因为无需判断是否添加过元素了，也就是不可能出现添加重复键，而且遍历次数是那个10个数乘积的平方根取整数。
其它的没什么，大致思路和我的一致，所以选他的回复修改下。
[解决办法]
我也来发一个，求约数个数的思想和6楼的差不多，分别对输入的数进行质因数分解，以达到对乘积进行质因数分解的目的。然后求约数个数，求的过程中都只取个位。
- C# code
namespace FindHero{ public class FindHero { public virtual int GetHeroID() { //对各CSDNer输入的数进行排序 SortByNuber(); //求各CSDNer输入的数进行质因数分解 GetSubmultiple(); //将上面的质因数分解结果汇总，即得各CSDNer输入的数的乘积的质因数分解结果 List<int> TotalDivisor = new List<int>(); for (int i = 0; i < CSDNerCount; ++i) { if (_people[i].Number != 1) { TotalDivisor.Add(_people[i].Number); } TotalDivisor.AddRange(_people[i].Divisor); } //对乘积的质因数分解的结果进行排序，以方便统计各质因数出现的次数 TotalDivisor.Sort(); int DivisorCount = 1, HeroID = 1; //统计各质因数出现的次数，同时计算约数个数的个位数 for (int i = 1; i < TotalDivisor.Count; ++i) { if (TotalDivisor[i] == TotalDivisor[i - 1]) { //如果这个质因数和上一个相同，则这个质因数的出现次数加一 ++DivisorCount; } else { //如果这是一个新的质因数，则进行计算，并重置计数器 HeroID = HeroID * (DivisorCount + 1) % 10;//计算约数的个数，但是只需要个位，所以取余 DivisorCount = 1; } } HeroID = HeroID * (DivisorCount + 1) % 10;//将最后一个质因数个数加入计算 return HeroID; } protected virtual void GetSubmultiple() { int StartIndex = 0; int[] HalfNumber = new int[CSDNerCount]; for (int i = 0; i < CSDNerCount; ++i) { HalfNumber[i] = (int)_people[i].Number / 2; } { int i = 2; while (i < HalfNumber[CSDNerCount - 1]) { bool flag; while (i > HalfNumber[StartIndex]) { ++StartIndex; } flag = true; for (int m = StartIndex; m < CSDNerCount; ++m) { if ((_people[m].Number % i) == 0) { _people[m].Number /= i; flag = false; _people[m].Divisor.Add(i); } } if (flag) { ++i; } } } } public virtual void SortByNuber() { int tmpNumber, tmpID; for (int i = 0; i < CSDNerCount - 1; ++i) { for (int m = i + 1; m < CSDNerCount; ++m) { if (_people[i].Number > _people[m].Number) { tmpNumber = _people[i].Number; tmpID = _people[i].ID; _people[i].Number = _people[m].Number; _people[i].ID = _people[m].ID; _people[m].Number = tmpNumber; _people[m].ID = tmpID; } } } } public struct Person { public int ID; public int Number; public List<int> Divisor; } public FindHero() { _people = new Person[CSDNerCount]; for (int i = 0; i < CSDNerCount; ++i) { _people[i].Divisor = new List<int>(); } } public int[] Numbers { get { int[] tmp = new int[CSDNerCount]; for (int i = 0; i < CSDNerCount; ++i) { tmp[i] = _people[i].Number; } return tmp; } set { for (int i = 0; i < CSDNerCount; ++i) { if (value[i] < MIN_VALUE || value[i] > MAX_VALUE) { throw (new OverflowException()); } _people[i].Number = value[i]; _people[i].ID = i; } } } protected const int CSDNerCount = 10, MIN_VALUE = 1, MAX_VALUE = 10000; protected Person[] _people; } class Program { static void Main(string[] args) { int[] Data = new int[10]; FindHero test = new FindHero(); for (int i = 0; i < 10; ++i) { while (!int.TryParse(Console.ReadLine(), out Data[i])) ; } test.Numbers = Data; Console.WriteLine(test.GetHeroID()); } }}
[解决办法]
怎么感觉题目有点问题啊，编号为0的是无论如何也不会被选到的呀
[解决办法]
[解决办法]
1,开辟一个整型数组a[10001],存放10个人的数字之积的各质因数的个数.初始为0
比如36=2^2 * 3^2,也就是说a[2]=2,a[3]=2,其他为0
此步复杂度为,10*(10000以内的数字求质因数个数的复杂度),可以搞个100以内的质数表,这个最多计算100次.总共10*100=1000
2,求此数的约数个数,其实就是把a[1]...a[10000]的值分别加1后相乘,10000复杂度.而且这个值不会越界
(a[2]+1)*(a[3]+1)=9
3,求2中得到的值的个数数即可.
[解决办法]
- -我去调试试试
匿
其实我好奇那哪个数字的可能性比较大
[解决办法]
说说我的看法， 每个人写的数字可以写成素数的乘积，则10个人的数字很容易也转成素数的乘积，在高代中有一个公式是可以计算的，a1^p1 * a2^p2...， 其中a1,a2这些全部是素数，则有因子数是（a1+1)(a2+1)(...).. 所以问题就解决了
[解决办法]
使用 2 作为 素数数组的第一个元素 ，初始明显是1
然后从3开始到最大数一直找，
去除 素数数组的每一个元素，用于判断 是否 是素数，
如果是素数， 加入到素数数组中，使其总数+1.
这样可快速得到 素数数组集合。
第二步，
使用这些素数 去 整除 之前的 那个乘积，
得到 若干 素数 和 此素数个数
则的 （num1+1）*(num2+1)...*(numn+1),
取个位，完毕。
[解决办法]
我刚学C，来试一下，不知是否对，还请楼主评判
#include<stdio.h>
#include<math.h>
#define N 10
void main()
{
int a[N],*p=a;
int j=0;
long int i,sum=1;
puts("Please input ten numbers:");
for(;p<N+a;p++)
{
scanf("%d",p);
}
for(p=a;p<N+a;p++)
sum*=*p;
for(i=1;i<=sum;i++)
{
if(sum%i==0)
j++;
}
printf("the number of common divisor is: %d\n",j);
}
[解决办法]
呵呵，合数都可以转化为X=a0^i*a1^i2....an^in的形式，而a0-an是小于10^4的素数，分别对每个数求出其含素数的个数[一个while即可]，然后统计在一起，可以用hash<int, int>来统计之。
然后的问题就是，a0^i1*a1^i2....an^in这种形式能组合出多少种不同约数，可以转化组合数也可以看为0，1背包，一定是 连乘(2^ix-1)[x->1...n]，最后与10求模，最终即为所求。代码就略去了，应该能在30-40行左右搞定。一点优化，个位肯定只由个位决定，所以连乘((2^ix-1)%10)可以避免越界哈！
楼主用心良苦，做应用的人还是应该多修内功，这个才是程序之道呀！下次发点DP之类的吧，比较练思维。
[解决办法]
我想这里还不如考虑改方案是否公平，是否有某种选数方案可以令部分人大大受益或者令部分人大大危险呢？
还有，我想问问34楼，为何说0号是无论如何都是免灾的呢？是说0号可以选某种号码，使得无论他人如何选数都不会波及自己吗？ 因为（比如）：如果有1人选1，9人选2，那么就是0号遭殃啦。
我想这个问题还是不简单的，
[解决办法]
1，2，6，1，3，1，1，1，1，1
对每个数分解得约数位：
1，2，2，3，3，1，1，1，1，1，1
然后每个数和剩余的数相乘得为要求的约数
重复的不统计。
时间复杂度起码有平方级，需优化。
[解决办法]
- C/C++ code
#include "stdio.h"#include "math.h"void main(){ long i,t,j=1,k=0; for(i=1;i<=10;i++) { scanf("%ld",&t); j*=t; } for(i=1;i<=j;i++) if(j%i==0) k++; printf("%d",k%10);}
[解决办法]
首先，简单的把10个数相乘，其结果范围在1～1e40,64位绝对容纳不下，而且效率低下
其次，要求约数的个数，可以使用排列组合的方法，计算每个质数的个数，
支持43楼
[解决办法]
这类比性能的算法最好提供一个统一的代码框架和测试数据。
- C# code
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{ class Program { static void Main(string[] args) { const int maxNumber = 1000; // 最大的数字范围 const int toll = 10; // 人数 #region 生成测试数据 //var cards = new int[] { 1, 2, 6, 1, 3, 1, 1, 1, 1, 1 }; var cards = new int[toll]; // 每个人写出的数字 var random = new Random(); for (var i = 0; i < cards.Length; i++) cards[i] = random.Next(maxNumber) + 1; #endregion 生成测试数据 #region 统计约数出现的次数 var divisor = new Dictionary<int, int>(); for (var j = 0; j < cards.Length; j++) { var i = 2; while (cards[j] > 1) { if (cards[j] % i == 0) { if (divisor.ContainsKey(i)) divisor[i]++; else divisor[i] = 1; cards[j] /= i; } else i += i == 2 ? 1 : 2; } } #endregion 统计约数出现的次数 #region 计算约数个数 var sum = 1; foreach (var i in divisor) if (i.Value > 0) sum *= (i.Value + 1); #endregion 计算约数个数 Console.WriteLine(sum % toll); Console.Read(); } }}
[解决办法]
[code=C/C++][/code]
#include<iostream.h>
void getHero(){
int incomeList[10];
int N=10000;
int i=0;
while(i<10){
cin>>incomeList[i];
if(incomeList[i]>0&&incomeList[i]<10000){
i++;
}
}
int prime[1250];
int tempList[1250];
int tag[10000];
int cnt = 0;
for (i = 2; i < N; i++)
{
if (!tag[i])
{
prime[cnt++] = i;
tempList[cnt]=0;
}
for (int j = 0; j < cnt && prime[j] * i < N; j++)
{
tag[i*prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
for(i=0;i<10;i++){
int temp = incomeList[i];
int j=0;
while(j<cnt-1 && temp>=prime[j]){
if(temp%prime[j]==0){
temp=temp/prime[j];
tempList[j]=tempList[j]+1;
}
else{
j++;
}
}
}
int aa=1;
for(i=0;i<cnt-1;i++){
if(tempList[i]>0){
aa=aa*(tempList[i]+1);
}
}
cout<<aa%10<<endl;
cin>>i;
}
int main(){
getHero();
}
用线性找一万以内的素数表，再依次记录每一个数中每个素数出现的次数。最后，将出现过的素数个数+1相乘，就可以得到结果。
比如如果在十个数中，5出现了3次，7出现了1次，则最后的因数个数一定是(3+1)*(1+1)=8个。
这个兄弟们自己证明一下哟。
这是我能想到的解决效率的办法了。有好办法记得跟我说一下。