首页 > 其他分享 >Codeforces Round #829 (Div. 2) D. Factorial Divisibility(数学)

Codeforces Round #829 (Div. 2) D. Factorial Divisibility(数学)

时间:2022-10-23 23:46:17浏览次数:120  
标签:题目 Divisibility Factorial tt Codeforces int 阶乘

题目链接


题目大意:

\(~~\)给定n个正整数和一个数k,问这n个数的阶乘之和能不能被k的阶乘整除
既:(a\(_{1}\)!+a\(_{2}\)!+a\(_{3}\)!+....+a\(_{n}\)!)\(~\)%\(~\)k!\(~\)==$~$0


题目分析:

我们把连续几个数的阶乘可以分解成如下结果:
\(~~~\)假设现在有3个2,4个3:
\(~~~\)那我们可以得到sum\(~\)=$~$3*2!+ 4*(3*2!)

\(~~~~~~~~~~~~~~~~~~~~~~~~~\)sum = 5*(3*2!)

通过如下过程我们就可以将低位阶乘转化为高位阶乘
那最终我们其实求得就是m*(k!) % k! == 0
所以我们就需要将所有的低位阶乘全部转化为高位阶乘,如果中间有不能转换的部分(既剩余部分),那就说明最终不能转化为k!的倍数,此时就为“No”


代码实现:

# include<iostream>
# include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 5e5 + 10;
int a[N];
void solve() {
	int n,k;
	cin>>n>>k;
	map<int,int> cnt;     //计数
	for(int i = 1;i <= n;++i){
		cin>>a[i];
		if(a[i]<k) cnt[a[i]]++;
	}
	for(int i = 1;i < k;++i){
		if(cnt[i]%(i+1))//若不能整除说明转化的时候会有剩余,则输出No
        {
			cout<<"No"<<endl;
			return;
		}
		cnt[i+1] += cnt[i]/(i+1);//低位转化到高位
	}
	cout<<"Yes"<<endl;
}
int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;


//	cin >> tt;
	while (tt--)solve();


	return 0;
}

标签:题目,Divisibility,Factorial,tt,Codeforces,int,阶乘
From: https://www.cnblogs.com/empty-y/p/16820063.html

相关文章

  • Codeforces 1682 D Circular Spanning Tree
    题意1-n排列,构成一个圆;1-n每个点有个值0或者1,0代表点的度为偶数,1代表点的度为计数;询问能否构成一棵树,树的连边在圆内不会相交,在圆边上可以相交,可以则输出方案。提示1.......
  • Codeforces Round #758 (Div.1 + Div. 2) C
    C.GameMaster//不明白为什么tag上没有二分我二分一下就过了我们显然知道判断是否能打赢全部直接通过连边来判断是否能遍历全部点如何连边:我们同组一定相连对于排......
  • CodeForces-1143#C 题解
    正文♦时间复杂度:\(\mathcal{O}(n)\)思维题,不需要建树。设数组\(a\)记录每一个节点是否尊重它的父节点,数组\(b\)记录是否有节点尊重它,特别的,叶子节点必然不被尊重。......
  • Educational Codeforces Round 138
    EducationalCodeforcesRound138这把是真的丢了大脸。Dashboard$\color{Green}{★}\\$表示赛时做出。$\color{Yellow}{★}\\$表示赛后已补。$\color{Red}{★}......
  • Codeforces 823B
    题意:对若干正整数二元组\((x_i,t_i)\),求一个实数\(x_0\),使得\(max\{t_i+|x_i-x_0|\}\)最小。n<=1e5。思考:​ 虽然问的是\(x_0\),但不妨对这个最小的最大值进行二分,也......
  • Educational Codeforces Round 138 (Rated for Div. 2) A-E
    比赛链接A题解知识点:贪心。注意到\(m\geqn\)时,不存在某一行或列空着,于是不能移动。而\(m<n\)时,一定存在,可以移动。时间复杂度\(O(1)\)空间复杂度\(O(1)\)代......
  • Dashboard - Educational Codeforces Round 138 (Rated for Div. 2) - Codeforces
    Dashboard-EducationalCodeforcesRound138(RatedforDiv.2)-Codeforces这场比赛写的就很菜了。D题有点思路但是没想到是求是去求不满足条件的序列。1.Problem......
  • Codeforces Round #828 (Div. 3)
    CodeforcesRound#828(Div.3)1.Problem-D-Codeforces只要找有因子2的个数即可。只要因子个数是大于等于n的即可。voidslove(){cin>>n;fel(i,1,n)cin......
  • Codeforces Round #756 (Div. 3) E1
    E1.EscapeTheMaze(easyversion)我们显然遍历根节点到叶结点的同时维护最短距离然后在return的时候看该点距离是否大于最近的朋友的距离要是大于的话我们显然可以......
  • Heidi and Library (hard) | CodeForces 802C最大流最小费用
    神仙题,想了两节ds课没想出来,跑到奇怪的犄角旮旯去了还是没法搞一个满意的模型看了洛谷黑题啊..释然了思路和细节在代码//LUOGU_RID:90857083#include<bits/stdc++.h......