Help us understand the problem. What is going on with this article?

abc 112 d 最大公約数

More than 1 year has passed since last update.

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;
}
tell0120xxx
21歳です。ゴミ記事を書きます
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした