Educational Codeforces Round 20 C. Maximal GCD

http://codeforces.com/contest/803/problem/C

N,K <= 10^10 이 주어졌을 때

N을 strictly increasing 하는 K개의 수로 분리하는데 이 K개의 수의 GCD가 최대가 되도록 하는 것이다.

만약 strictly increasing 하는 K개의 수로 분리가 불가능하다면 -1을 출력한다. 답이 여러개라면 아무거나 출력한다.

우선 GCD가 1보다 큰 K개의 수로 N을 나타냈다고 쳐보자. 그럼 K개의 수를 각각 GCD로 나누고 N도 GCD로 나눠보자

그러면 이것은 N/GCD 를 strictly increasing 하는 K개의 수로 나눈 것이 된다.

그리고 N을 K개의 strictly increasing 하게 분리가능한 가장 작은 N은 역시 1,2,3....,K 로 나누는 경우이기 때문에 K*(K+1)/2 가 된다.

그렇기 때문에 N이 'strictly increasing 한 K개로 분리가능한가' 라는 말과 N >= K*(K+1)/2 냐 라는 말이 같고

먼저 GCD를 정해주고 이 GCD로 strictly increasing 하는 K개로 분리가 가능한지

즉, 고정된 GCD로 K개의 수를 각각 나눠서 모두 더한 값이 K*(K+1) 보다 크거나 같은지를 판단하기만하면되기 때문에

GCD를 최대로 하기위해 가능한 가장 큰 GCD부터 가장 작은 GCD까지 반복하며 가장 큰 GCD를 찾은 뒤

N을 그 GCD로 나눠서 strictly increasing 한 K개의 수를 만들고(1,2,3,... 처럼 1씩 증가시키다가 마지막 K번째 수에 다 때려박으면됨)

K개의 수에 모두 GCD를 곱해주면 답이 될 것이다.

만약 N/GCD >= K*(K+1)/2 가 되는 GCD가 없다면 답이 없는것이다.

그럼 GCD 를 정해준다는 말은 N 이 GCD로 나눠진다는 말이며(K개의 수의 합을 나타내는 식에서 GCD를 묶어서 뺄수있으므로)

그럼 가능한 GCD의 목록은 결국 N의 약수들이라는 것이다. 그렇기 때문에 N의 모든 약수들을 큰 수에서부터 봐주면된다.

아주아주 큰 N의 모든 약수를 구하는 방법은 N^0.5 까지 돌면서 N를 나눌 수 있는 수 i와 N/i를 같이 넣어주는 방법이다.

왜냐하면 약수들은 대칭성(?)을 가지기 때문에 i가 약수라면 N/i 도 무조건 약수이다. 물론 i 가 N^0.5일 때는 중복을 피하기위해

한번 더 넣지 않도록 예외처리를 해주면 된다.

그런데 여기서 유의해줘야 할 것이 있다. 아마 출제자의 노림수 같은데 K는 최대 10^10 이기 때문에 long long 으로 해도

제곱을 해버리면 overflow 가 난다.... 그렇기 때문에 K가 너무 크면 어차피 답이 없기 때문에(K개의 수를 모두 더한 값이

N이 되어야 하는데 그럼 strictly increasing 한 K개의 수의 합이 N이 되도록 할 수 있는 가장 큰 K는 N == K*(K+1)/2 인 K 이기 때문에

대충 분리가능한 최대 K는 N^0.5 보다 좀더 큰값 까지 정도이다. N의 최대값이 10^10 이므로 한 10^7가 넘으면

무조건 -1을 출력하도록 하면된다.

처음에 나는 전에 풀었던 어떤 문제가 떠올렸는데 그 문제는 소인수 분해를 해야 됐고 제약도 좀 더 크고 했는데

그땐 소인수들에 대해 포함배제의 원리를 사용해야 했기 때문에 에라토스테네스의 체로 가능한 범위의 소수들을 구하고

그 소수들로 소인수 분해를 한뒤 그 소인수들로 모든 약수들을 구했는데

이 문제는 약수를 구하기 위해 굳이 '소인수'를 구해서 약수를 구할 필요가 전혀 없고

그냥 바로 약수를 구하면 되고 모든 약수를 구하는 것이 훨씬 간단하기 때문에(루트까지만 돌려서 반대쪽꺼도 넣어주면됨)

이렇게 복잡하게 할 필요가 없었다..

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
ll N,K;
vl divisors;
int size;
int main() {
    scanf("%lld%lld",&N,&K);
 
    if(K>1e9){
        printf("-1");
        return 0;
    }
    ll ans = -1;
    for(ll i = 1; i * i <= N; i++){
        if(N%i==0){
            divisors.pb(i);
            if(i != N/i) divisors.pb(N/i);
        }
    }
    sort(all(divisors));
    FOR(i,sz(divisors)){
        if(divisors[i] >= K*(K+1)/2) {
            ans = divisors[i];
            break;
        }
    }
    if(ans==-1) {
        printf("-1");
        return 0;
    }
    for(ll i = 1; i <= K; i++){
        if(i!=K){
            printf("%lld ",i*(N/ans));
        }
        else {
            printf("%lld ",(ans-(K*(K-1)/2))*(N/ans));
        }
    }
    return 0;
}