M_sea

CF803C Maximal GCD
CodeforcesLuogu分析设答案为 $d$ ,那么显然 $n$ 是 $d$ 的倍数。于是可以枚举 $n$ ...
扫描右侧二维码阅读全文
07
2019/09

CF803C Maximal GCD

Codeforces

Luogu

分析

设答案为 $d$ ,那么显然 $n$ 是 $d$ 的倍数。

于是可以枚举 $n$ 的约数。于是只要考虑如何判断一个 $d$ 是否合法。

显然,可以构造一个首项为 $d$ ,末项为 $dk$ 的等差数列,在此基础上再在末项上加一个数 $c$ 使得整个数列的和为 $n$ 的倍数。

那么就很容易判断了。但是要注意判的时候会爆 long long ,需要开 double

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

ll n,k,ans=-1;

inline void check(ll d) {
    if ((d+1.0*d*k)*k/2>n) return;
    ll s=(d+d*k)*k/2;
    if ((n-s)%d) return;
    ans=max(ans,d);
}

int main() {
    n=read(),k=read();
    for (re ll d=1;d*d<=n;++d) {
        if (n%d) continue;
        check(d),check(n/d);
    }
    if (ans==-1) puts("-1");
    else {
        for (re int i=1;i<k;++i) printf("%lld ",ans*i);
        printf("%lld\n",(n-(ans+ans*(k-1))*(k-1)/2));
    }
    return 0;
}
最后修改:2019 年 09 月 07 日 07 : 22 PM

发表评论