ARC004 C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )
問題ページ
C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )
考えたこと
- 数式を書いてみると X/Y = (N(N+1)/2 - M) / N
- N = Y/2, M = (Y^2+2Y-4X)/8
- N,Mが整数かつN < Mの条件を満たすような(X, Y)の組を探す
- N<Mの条件を満たす間(X, Y) (2X, 2Y) (3X, 3Y) … について探索していく
- これで出すとTLEしたのでMがマイナスになる部分を枝刈りする
- (kY)^2 + 2kY - 4kX > 0 を満たすように整数kを選ぶ
- k = 0, (4X - 2Y)/Y^2 になったのでMがマイナスだったら (4X - 2Y)/Y^2 をX, Yに掛けてから探索を始めることにして投げたら通った
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back #ifdef int const ll INF = (1LL<<60); #else const int INF = (1LL<<30); #endif const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { int x, y; char c; cin >> x >> c >> y; int g = __gcd(x, y); x /= g, y /= g; if(y%2) x *= 2, y *= 2; vector<PII> v; int xx = x, yy = y; if(yy*yy+2*yy < 4*xx) { int k = (4*xx - 2*yy)/(y*y); k = max(1LL, k-3); // cout << k << endl; xx *= k, yy *= k; } while(true) { // cout << xx << " " << yy << " " << yy/2 << " " << (yy*yy+2*yy-4*xx)/8 << endl; if(yy/2 < (yy*yy+2*yy-4*xx)/8) { break; } if(yy%2 != 0) { xx += x, yy += y; continue; } if((yy*yy+2*yy-4*xx)%8 != 0) { xx += x, yy += y; continue; } if(yy/2 <= 0 || (yy*yy+2*yy-4*xx)/8 <= 0) { xx += x, yy += y; continue; } v.PB({yy/2, (yy*yy+2*yy-4*xx)/8}); xx += x, yy += y; } if(v.size() == 0) cout << "Impossible" << endl; else { for(auto i: v) cout << i.first << " " << i.second << endl; } return 0; }