abc 112 d 最大公約数 #C++

悩んでる暇があったら全探索

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<cmath>
#include<map>
using namespace std;
using ll = long long;
const int INF = 1e9;
#define rep(i,n)for(int i=0;i<n;++i)
#define p pair<int,int>
int main() {
    int N;
    cin >> N;
    vector<ll>vx(N), vy(N), vh(N);
    int si = -1;
    for (int i = 0; i < N; ++i) {
        cin >> vx[i] >> vy[i] >> vh[i];
        if (vh[i] > 0)
            si = i;
    }
    ll resx = -1, resy = -1, resh = -1;
    for (ll x = 0; x <= 100; ++x) {
        for (ll y = 0; y <= 100; ++y) {
            ll h = vh[si] + abs(x - vx[si]) + abs(y - vy[si]);
            bool ok = true;
            for (int i = 0; i < N; ++i) {
                if (vh[i] > 0 && h - vh[i] != abs(x - vx[i]) + abs(y - vy[i]))
                    ok = false;
                if (vh[i] == 0 && h > abs(x - vx[i]) + abs(y - vy[i]))
                    ok = false;
            }
            if (ok)
                resx = x, resy = y, resh = h;
        }
    }
    cout << resx << " " << resy << " " << resh << endl;
    return 0;
}

D
整数N,Mが与えられる。
a1+a2+....aN=Mを満たす正の整数列a1,a2,,,aNをすべて考えた時のa1,a2,,,aNの最大公約数の最大値を求めよ

数学チックになってきた。
まずこれが必ずMの約数になることがわかる。
d=GCD(a1,a2,,,,,aN)とする。
このときa1,a2,,,aNはすべてdの倍数である。よってa1+a2+.....aNもdの倍数である。つまりdはMの約数である。
このうち最大を求めたい。
d=GCD(a1,a2,,,aN)とするとai>=dなのでNd<=Mである。これさえ満たしていれば必ずそういうa1,a2,,,aNは作れることがわかる。
具体的にはa1=d,a2=d,,,,aN-1=d,aN=M-(N-1)dとすればよい
まとめると答えはMの約数dのうちNd<=Mを満たす最大のものとなる。

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<cstdio>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 7;
//約数列挙
vector<ll>calc_divisor(ll n) {
    vector<ll>res;
    for (ll i = 1LL; i*i <= n; ++i) {
        if (n%i == 0) {
            res.push_back(i);
            ll j = n / i;
            if (j != i)res.push_back(j);
        }
    }
    sort(res.begin(), res.end());
    return res;
}
int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll>div = calc_divisor(M);

    //Mの約数dであって、d*N<=Mとなる最大のdを求める
    ll res = 1;
    for (ll i = 0; i < div.size(); ++i) {
        if (div[i]*N <= M) {
            res = max(res, div[i]);
        }
    }
    cout << res << endl;
    return 0;
}