ferinの競プロ帳

競プロについてのメモ

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;
}