日期:2014-05-20  浏览次数:21357 次

【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);
                }
            }
        }
    }
}