結果

問題 No.176 2種類の切手
コンテスト
ユーザー snrnsidy
提出日時 2023-05-14 21:05:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,415 bytes
コンパイル時間 2,562 ms
コンパイル使用メモリ 375,880 KB
最終ジャッジ日時 2025-02-13 00:35:04
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 3 TLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")	
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping") 
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma") 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 
//#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

__int128 gcd(__int128 a,__int128 b)
{
  if(a < 0) a*=-1;
  if(b < 0) b*=-1;
  if(b>0) return gcd(b,a%b);
  return a;
}

__int128 inv(__int128 a,__int128 m)
{
  __int128 m0 = m, y = 0, x = 1;
  if(m==1) return 0;
  while(a>1)
  {
    __int128 q = a/m;
    __int128 t = m;
    m = a%m;
    a = t;
    t = y;
    y = x - q*y;
    x = t;
  }
  if(x<0) x += m0;
  return x;
}

bool func(__int128 A,__int128 B,__int128 C)
{
  if(A==0 && B==0)
  {
    if(C==0)
    {
      return true;
    }
    else
    {
      return false;
    }
  }
  if(A==0)
  {
    if(C%B==0) return true;
    else return false;
  }
  if(B==0)
  {
    if(C%A==0) return true;
    else return false;
  }

  __int128 g = gcd(A,B);
  if(C%g!=0)
  {
    return false;
  }
  if(g > 1)
  {
    return func(A/g,B/g,C/g);
  }
  else
  {
    __int128 c = inv(A,B);
    __int128 x = (c*C)%B;
    __int128 y = (C - (A*x))/B;
    if(y<0)
    {
      return false;
    }
    while(gcd(x,y)!=1 && y>=0)
    {
      x += B;
      y -= A;
    }
    if(y<0)
    {
      return false;
    }
    return true;
  }
  return false;
}
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

	long long int A,B,C;

	cin >> A >> B >> C;

    long long int g = gcd(A,B);

    long long int x = ceil((C*1.0)/g);

    while(1)
    {
        if(func(A,B,x*g))
        {
            cout << x*g << '\n';
            break;
        }
        x++;
    }
    return 0;
}
0