首页 > 其他分享 >Acwing 197 阶乘分解

Acwing 197 阶乘分解

时间:2023-08-18 22:33:38浏览次数:42  
标签:int 197 long 阶乘 Acwing getchar

我觉得都不用过多解释,看代码就懂了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int read()
{
	int x=0;
	char s=getchar();
	while(s<'0'||s>'9')
	{
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=(x<<3)+(x<<1)+s-48;
		s=getchar();
	}
	return x;
}
int prime[N],v[N];
int cnt;
void getprime(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!v[i])
		{
		    v[i]=i;
		    prime[++cnt]=i;
		}
		for(int j=1;j<=cnt&&prime[j]*i<=n&&prime[j]<=v[i];j++)
		v[prime[j]*i]=prime[j];
	}
}
int n;
ll c[N];
int main()
{
	int a,u;
    n=read();
	getprime(n);
	for(int i=2;i<=n;i++) c[i]=1;
	for(int i=n;i>=2;i--) 
	if(v[i]!=i)
	{
	    c[v[i]]+=c[i];
	    c[i/v[i]]+=c[i];
	}
	for(int i=1;i<=cnt;i++)
	printf("%d %lld\n",prime[i],c[prime[i]]);
    return 0;
}

标签:int,197,long,阶乘,Acwing,getchar
From: https://www.cnblogs.com/dingxingdi/p/17641749.html

相关文章

  • AcWing 860. 染色法判定二分图
    题目给定一个$n$个点$m$条边的无向图,图中可能存在重边和自环。请你判断这个图是否是二分图。输入格式第一行包含两个整数$n$和$m$。接下来$m$行,每行包含两个整数$u$和$v$,表示点$u$和点$v$之间存在一条边。输出格式如果给定图是二分图,则输出Yes,否则输出No......
  • C# 表达式体方法 C#算阶乘
    //表达式体方法privateintAdd(inta,intb)=>a+b;[Fact]publicvoidTest(){varresult1=Factorial(1);//1varresult2=Factorial(2);//2varresult3=Factoria......
  • AcWing 858. Prim算法求最小生成树
    题目给定一个$n$个点$m$条边的无向图,图中可能存在重边和自环,边权可能为负数。求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。给定一张边带权的无向图$G=(V,E)$,其中$V$表示图中点的集合,$E$表示图中边的集合,$n=|V|,m=|E|$。由$V$中的全部$n$个......
  • AcWing 854. Floyd求最短路
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,边权可能为负数。再给定$k$个询问,每个询问包含两个整数$x$和$y$,表示查询从点$x$到点$y$的最短距离,如果路径不存在,则输出impossible。数据保证图中不存在负权回路。输入格式第一行包含三个整数$n,m,k......
  • AcWing 852. spfa判断负环
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,边权可能为负数。请你判断图中是否存在负权回路。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整数$x,y,z$,表示存在一条从点$x$到点$y$的有向边,边长为$z$。输出格式如果图中存在负......
  • Acwing第116场周赛
    Acwing.第116场周赛这次做的稍微通畅一点,但是做到第三题还是发懒了,以后每次周赛打完都会有一个周赛总结第一题:简单判断给定三个非负整数x,y,z,请根据如下要求进行判断并输出结果:如果x>y+z,输出+;如果y>x+z,输出-;如果x=y并且z=0,则输出0;如果以上都不满足,则输出?......
  • AcWing116
    AcWing116AAcWing5134.简单判断voidsolve(){intx,y,z;cin>>x>>y>>z;if(x>y+z)cout<<'+'<<endl;elseif(y>x+z)cout<<'-'<<endl;elseif(x==......
  • AcWing 851. spfa求最短路
    题目给定一个$n$个点$m$条边的有向图,图中可能存在重边和自环,边权可能为负数。请你求出$1$号点到$n$号点的最短距离,如果无法从$1$号点走到$n$号点,则输出impossible。数据保证不存在负权回路。输入格式第一行包含整数$n$和$m$。接下来$m$行每行包含三个整......
  • acwing 116.飞行员兄弟 (算法竞赛进阶指南 p48 t1 ) 题解
    原题链接https://www.acwing.com/problem/content/description/118/题目描述“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有16个把手的冰箱。已知每个把手可以处于以下两种状态之一:打开或关闭。只有当所有把手都打开时,冰箱才会打开。把手可以表示为一个4х4的矩阵,您可以......
  • (简单)计算斐波那契数列与阶乘
    斐波那契数列pythondeffibonacci(n):ifn<=0:return"Invalidinput"elifn==1:return0elifn==2:return1else:prev_1=0prev_2=1for_inrange(n-2):curre......