Ural Brave Balloonists
题目大意:给定10个数ai(1<=ai<=10000),m=a1*a2*…*a9*a10,求m的所有正约数的数量sum,输出sum%10.
分析:首先求1~10000内的所有素数,然后分解每一个ai,让对应素数的系数相加得到ei,最后求sum%10=(e1+1)*(e2+1)*…*(e9+1)*(e10+1)%10.
涉及算法:素数筛选法及分解质因数
代码:
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
const int maxn=10010;
struct node
{
int p;//存储素数
int num;//存储相对应素数的系数
node(int a=0,int b=0):p(a),num(b){}
}prime[maxn];//素数表
int pnum;//记录1~maxn内素数的数量
void getPrime()
{//应用素数筛选法得到素数表
pnum=0;
prime[pnum++]=node(2,0);
for(int i=3;i<=maxn;i+=2)
{
bool isprime=true;
int cap=sqrt((double)i)+1;
for(int j=0;j<pnum;j++)
{
if(prime[j].p>=cap) break;
if(i%prime[j].p==0) {isprime=false;break;}
}
if(isprime) prime[pnum++]=node(i,0);
}
}
int main()
{
int n;
getPrime();
for(int i=1;i<=10;i++)
{
scanf("%d",&n);
for(int j=0;j<pnum;)
{//得到系数
if(n%prime[j].p==0) {prime[j].num++;n/=prime[j].p;}
else j++;
}
}
int sum=1;
for(int i=0;i<pnum;i++)
{
sum=sum*(prime[i].num+1)%10;
}
printf("%d\n",sum);
return 0;
}
分享到:
相关推荐
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
Ural
URAL3D
Pascal acm_timus_ural_1148.pas
URAL(Timus Online Judge)部分测试数据 不全
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
Pascal acm_timus_ural_1099.pas
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
URAL-PHA
Ural ACM 1000源代码(c++),vc++6.0在XPsp2下编译通过,Timus Online Judge再线测评通过
因为大三了 不弄ACM了 所以这些就删了 删之前希望可以帮到别人
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->...ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
基于张量类模板的线性代数C ++库,可用于表示等级0的张量,标量向量,1的向量,2的矩阵,3的等级3的张量等。它还包括BLAS和LAPACK子例程的接口。
28. The Theoretical Background of the Ural-Altale Hypothesis The hypothesis of common origin of the Altaic languages,and even the Ural-Altaic languages,dates from the first half of the last century....
乌拉尔
Philip_Dural_UX-UI_Designer:UXUI设计器配置文件
资源分类:Python库 所属语言:Python 资源全名:ural-0.25.0-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059