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
输出: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()); }
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);
}
}
}
}
}
杜绝跨省追捕
你的帖子在asp.net,我怎么推荐啊?
其实之前就有大批人对新版不爽,没有办法的,即使联名抗议了也不一定会有用。
这个版面影响大家积极性
发这里会被你搞掉
你直接帮我搞非技术区了
呵呵asp.net版面环境宽松
目前只要输出谁被kill掉即可。
是根本没用!下次楼主推荐一些牛X点的算法贴吧。本身,我觉得,推荐到首页上去,让人家一看.net版的推荐算法贴仅仅是……是吧……
#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;
}
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);
} //分解P,表示为 a1^b1+a2^b2+...的形式
private static void Split(int p)
{
if (p == 1)
{
return;
}
if (dItems.ContainsKey(p)) //p是质数
{
dItems[p]++;
return;
} int[] tmp = new int[dItems.Count];
dItems.Keys.CopyTo(tmp, 0);
foreach (int i in tmp)
{
if (i > p || p <= 1)
{
break;
}
while (p % i == 0 && p > 1)
{
dItems[i]++;
p /= 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);
}
}
}
}
}
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;
return 1;
}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;
}
改正了
#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;
return 1;
}int SelectPerson(int *p)
{
int sum = 1;
int index = 1;
for(int i = 0; i < 10; i++){
sum *= p[i];
}
if(sum == 1 ) return sum;
cout << sum <<endl;
for(int j = 1; j <= sum/2; j++){
if(sum%j == 0){
index++;
}
}
return index;
}
HashTable似乎没有List效率高,if (_HashValue[_ValueNumb] == null)这个判断多余了,因为添加的元素就是null,所以就算存在也是null,等号永远成立,不过后面的添加会报错,因为出现重复键了。
if (_Numb == _Value) break; 改为if (_Numb == _ValueNumb ) break; 的话,效率会更高,因为无需判断是否添加过元素了,也就是不可能出现添加重复键,而且遍历次数是那个10个数乘积的平方根取整数。
其它的没什么,大致思路和我的一致,所以选他的回复修改下。
HashTable似乎没有List效率高,if (_HashValue[_ValueNumb] == null)这个判断多余了,因为添加的元素就是null,所以就算存在也是null,等号永远成立,不过后面的添加会报错,因为出现重复键了。
if (_Numb == _Value) break; 改为if (_Numb >= _ValueNumb ) break; 的话,效率会更高,因为无需判断是否添加过元素了,也就是不可能出现添加重复键,而且遍历次数是那个10个数乘积的平方根取整数。
其它的没什么,大致思路和我的一致,所以选他的回复修改下。
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());
}
}
}
比如36=2^2 * 3^2,也就是说a[2]=2,a[3]=2,其他为0
此步复杂度为,10*(10000以内的数字求质因数个数的复杂度),可以搞个100以内的质数表,这个最多计算100次.总共10*100=10002,求此数的约数个数,其实就是把a[1]...a[10000]的值分别加1后相乘,10000复杂度.而且这个值不会越界
(a[2]+1)*(a[3]+1)=93,求2中得到的值的个数数即可.
上面有人说了...0的可能性最大...
考查约数个数公式 (a1+1)(a2+1)(a3+1)...,只要所有乘数中出现一个10的倍数,或者同时有5和2的倍数, 0号就悲剧了-_-
去除 素数数组的每一个元素,用于判断 是否 是素数,
如果是素数, 加入到素数数组中,使其总数+1.这样可快速得到 素数数组集合。
第二步,
使用这些素数 去 整除 之前的 那个乘积,
得到 若干 素数 和 此素数个数
则的 (num1+1)*(num2+1)...*(numn+1),取个位,完毕。
#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);}
然后的问题就是,a0^i1*a1^i2....an^in这种形式能组合出多少种不同约数,可以转化组合数也可以看为0,1背包,一定是 连乘(2^ix-1)[x->1...n],最后与10求模,最终即为所求。代码就略去了,应该能在30-40行左右搞定。一点优化,个位肯定只由个位决定,所以连乘((2^ix-1)%10)可以避免越界哈!
楼主用心良苦,做应用的人还是应该多修内功,这个才是程序之道呀!下次发点DP之类的吧,比较练思维。
好像更简单了,只要求两自然数相乘,个位数的几率就好了static void Main(string[] args)
{
double[] module = new double[10]; //放10个数,第i位是指i乘以随机数后个位为i的几率。
//计算module
for (int i = 0; i < 10; i++)
{
module[i] = 0;
}
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
module[i * j % 10] += 0.1;
}
} //输出
double s = 0;
for (int i = 0; i < 10; i++)
{
s += module[i];
Console.WriteLine("rate of {0}: {1:00.00}%", i, module[i] * 10);
}
Console.Read();
}
rate of 0: 27.00%
rate of 1: 04.00%
rate of 2: 12.00%
rate of 3: 04.00%
rate of 4: 12.00%
rate of 5: 09.00%
rate of 6: 12.00%
rate of 7: 04.00%
rate of 8: 12.00%
rate of 9: 04.00%
这里要的是约数的个数,不应该只算一部分的, j<=sum,而不是sum/2
57楼笔误,因子数是:(q1+1)(q2+1)。而非(a1+1)(a2+1)...
56 楼逻辑有误:因子公式已经指出了,每个人都可以为改变表达式的积做出贡献,比如:
(1) 如果前面九个人的连乘积是:(q1+1)*(q2+1)*...*(q9+1),那么,如果你想改变其中第二和第五个的乘项,就令你的选号比如是a5的Q5次方与a2的Q2次方的乘积,这样,表达式中的第五项和第二项就发生了变化,很有可能导致最后的结果的个位数也发生变化,
(2)由此,0号选手可能不经意间就对另9个表达式的乘积产生了重大改变,所以,仅仅根据这个公式,不能
直接得出0号存在必死的可能
#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);
}
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();
}
}
}
蹭分
#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个。
这个兄弟们自己证明一下哟。
这是我能想到的解决效率的办法了。有好办法记得跟我说一下。