「CF803C」 Maximal GCD

比眉伴天荒 2023-08-17 17:24 57阅读 0赞

### 题目链接 ###

[戳我][Link 1]

### \\(Solution\\) ###

令\\(gcd\\)为\\(x\\),那么我们将整个序列\\(/x\\),则序列的和就变成了\\(\\frac\{n\}\{x\}\\),所以\\(x\\)必定为\\(n\\)的约数所以现在就是要构造出一个序列长度为\\(k\\),和为\\(\\frac\{n\}\{x\}\\)。我们令前\\(k-1\\)个为\\(1,2....k-1\\)最后一个再用\\(\\frac\{n\}\{x\}-\\)这\\(k-1\\)个的和就是最后一个数了。最后的答案就是构造出来的序列\\(\*x\\)

所以我们现在就是要来判断\\(x\\)可不可行，很明显如果\\((1+k)\*k/2>\\frac\{n\}\{x\}\\)的话显然不可行，反之则可以。所以我们找到最大的\\(x\\)用上述方法构造即可.

注意特判一下\\(k\\)很大的时候，有可能会乘爆

### \\(Code\\) ###

#include<bits/stdc++.h> #define int long long #define rg register #define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout); using namespace std; int read(){ int x=0,f=1;char c=getchar(); while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0'&&c<='9') x=x*10+c-48,c=getchar(); return f*x; } int n,k,maxx,ans; bool check(int x){ return (1+k)*k/2<=(n/x); } main(){ n=read(),k=read(); if(k>2e5) puts("-1"),exit(0); for(int i=1;i*i<=n;i++){ if(n%i!=0) continue; if(check(i)) maxx=max(maxx,i); if(check(n/i)) maxx=max(maxx,n/i); } if(!maxx) puts("-1"),exit(0); for(int i=1;i<=k-1;i++) cout<<i*maxx<<" ",ans+=i*maxx; cout<<n-ans; return 0; }

转载于:https://www.cnblogs.com/hbxblog/p/11415065.html

[Link 1]: https://www.luogu.org/problem/CF803C

发表评论取消回复

表情：

评论列表（有 0 条评论，57人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1217C

CF1217C 题意： > 给定一个01串，一个good01串的定义是这个01串所代表的二进制数字刚好等于它的长度，允许前导零，问这个01串当中有几个goo...

柔光的暖阳◎/ 2024年04月20日 10:34/ 0 赞/ 5 阅读

相关 CF1214C

CF1214C 题意： > 给你一个括号序列，问你时候能仅移动相邻的两个元素，使括号序列合法。解法： > 可以先考虑普通括号序列怎么做 > 这...

亦凉/ 2024年04月20日 10:33/ 0 赞/ 4 阅读

相关 CF1200C

CF1200C 题意： > 问内圆和外圆分别分成n、m份，每份有标号，问是否可以从一个部分走到另一个部分，12点钟位置一定有个线。解法： > 如果...

旧城等待，/ 2024年04月20日 10:32/ 0 赞/ 6 阅读

相关 CF1030C

CF1030C 题意： > 给你一个数字，问能否拆分成k段，使得每一段的每一位数字相加结果相等。解法： > 考虑数位DP。 > 暴力按位考虑每...

ゝ一纸荒年。/ 2024年04月20日 10:31/ 0 赞/ 5 阅读

相关「CF803C」 Maximal GCD

题目链接 [戳我][Link 1] \\(Solution\\) 令\\(gcd\\)为\\(x\\),那么我们将整个序列\\(/x\\),则序列的和就变成了\\

比眉伴天荒/ 2023年08月17日 17:24/ 0 赞/ 58 阅读

相关 C - 又见GCD

C - 又见GCD HPU专题训练（-1）GCD&&素筛&&快速幂\_\_\_\_\_C - 又见GCD 有三个正整数a,b,c(0<a,b,c<10^6)，

绝地灬酷狼/ 2022年06月01日 07:51/ 0 赞/ 159 阅读

相关 D. Zero Quantity Maximization（CF： Codeforces Round #544 (Div. 3)）

题目描述： You are given two arrays aa and bb, each contains nn integers. You want to cre

墨蓝/ 2022年03月11日 16:50/ 0 赞/ 123 阅读

相关 CF623B Array GCD

[CF623B Array GCD][] > 给定一个序列 \\(a\_i\\) ，可以进行一下两种操作： > > 删除一段长度为 \\(m\\) 的区间 \\((m

朱雀/ 2021年11月29日 12:18/ 0 赞/ 190 阅读

相关 cf 1179 C

目录 A B C A 模拟出A不是最大值的情况，存起来。最多有n个。当A为最大值的时候，后面n-1个数开始循环。查询分两种情况讨论就行了

比眉伴天荒/ 2021年11月01日 10:20/ 0 赞/ 187 阅读

相关 [CF803D] Magazine Ad（二分，贪心）

题意：字符串希望拆分成不大于k段，问如何拆分，使得每一行的字符串最短。其中有两个条件：空格或者连字符

你的名字/ 2021年01月08日 13:35/ 0 赞/ 393 阅读