「CF803C」 Maximal GCD

比眉伴天荒 2023-08-17 17:24 121阅读 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 条评论，121人围观）

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

相关阅读

相关【枚举gcd】CF803 C

[Problem - C - Codeforces][] 题意： ![c0f74c9a05f2451ead3cf4587dd84218.png][] 思路：要使所有数

落日映苍穹つ/ 2024年03月23日 22:42/ 0 赞/ 63 阅读

相关【二分答案】CF803 D

感觉之前的\1900好简单 [Problem - D - Codeforces][] 题意： ![47e9ce79fee54c63a55acba3cac6e937.pn

客官°小女子只卖身不卖艺/ 2024年03月23日 22:41/ 0 赞/ 48 阅读

相关【枚举倍数+容斥】CF803 F

[Problem - F - Codeforces][] 题意： ![e3f914ba017f4d068fe0f661eb611e23.png][] 思路：正难则反，

╰+哭是因爲堅強的太久メ/ 2024年03月23日 22:41/ 0 赞/ 45 阅读

相关【gcd】CF826div2 B

有人不会div2 B 没关系，精神稳定一分钟也很厉害了嘻嘻，嘻嘻.... [Problem - B - Codeforces][] ![2ad3819b26264c2

不念不忘少年蓝@/ 2024年03月22日 17:20/ 0 赞/ 50 阅读

相关【gcd】CF6691div1 A. Row GCD

[Problem - A - Codeforces][] 题意： ![7380f034bb90485e9e0d58dcfe3f9919.png][] 思路：辗转相除法

忘是亡心i/ 2024年03月22日 13:27/ 0 赞/ 44 阅读

相关【MST+GCD】CF714div2 D. GCD and MST

第一次写2000分的题，把大致思路想出来了但是差点细节比如vis数组没加，区间贡献算错了对于这些，思路对的但是差点细节的题，应该多模拟样例，不然写出来会很抽象 [

朱雀/ 2024年03月22日 13:13/ 0 赞/ 42 阅读

相关「CF803C」 Maximal GCD

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

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

相关 CF 678C 暑假集训13(gcd,lcm)

网址：http://codeforces.com/problemset/problem/678/C 题目大意：有1~n，n个数，如果k为a的倍数就给p个巧克力，k为

蔚落/ 2022年09月25日 11:20/ 0 赞/ 34 阅读

相关 CF623B Array GCD

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

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

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

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

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