結果

問題 No.3301 Make Right Triangle
ユーザー alcea
提出日時 2025-10-05 14:30:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 482 ms / 2,000 ms
コード長 2,744 bytes
コンパイル時間 2,073 ms
コンパイル使用メモリ 205,416 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-05 14:30:36
合計ジャッジ時間 10,371 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
bool MillerRabin(long long n,vector<long long> A){
  long long D,s,t,d,x;
  uint64_t mod=n,imod=n,t128=-__uint128_t(n)%n,m1;
  s=__builtin_ctzll(n-1);
  D=n-1>>s;
  for(int i=0;i<5;i++) imod*=2-mod*imod;
  imod=-imod;
  m1=(t128+__uint128_t(t128*imod)*mod)>>64;
  if(m1>=n) m1-=n;
  for(auto a:A){
    if(n<=a) return true;
    a=(__uint128_t(a)*t128+__uint128_t(a*t128*imod)*mod)>>64;
    if(a>=mod) a-=mod;
    x=m1;
    for(d=D;d>0;d>>=1){
      if(d&1){
        x=(__uint128_t(a)*x+__uint128_t(a*x*imod)*mod)>>64;
        if(x>=mod) x-=mod;
      }
      a=(__uint128_t(a)*a+__uint128_t(a*a*imod)*mod)>>64;
      if(a>=mod) a-=mod;
    }
    if(x!=m1){
      for(t=0;t<s;t++){
        if(x==mod-m1) break;
        x=(__uint128_t(x)*x+__uint128_t(x*x*imod)*mod)>>64;
        if(x>=mod) x-=mod;
      }
      if(t==s) return false;
    }
  }
  return true;
}
bool IsPrime(long long n){
  if(n<=1) return false;
  else if(n==2) return true;
  else if(n%2==0) return false;
  else if(n<4759123141LL) return MillerRabin(n,{2,7,61});
  else return MillerRabin(n,{2,325,9375,28178,450775,9780504,1795265022});
}
long long FindPrimeFactor(long long n){
  if(n%2==0) return 2;
  uint64_t mod=n,imod=n;
  for(int i=0;i<5;i++) imod*=2-mod*imod;
  imod=-imod;
  long long m=pow(n,0.15)+1,y,g,q,r,k,x,ys,d,c=1;
  auto f=[&](long long v){
    v=(__uint128_t(v)*v+__uint128_t(v*v*imod)*mod)>>64;
    if(v>=mod) v-=mod;
    v+=c;
    if(v>=mod) v-=mod;
    return v;
  };
  for(;true;c++){
    y=k=0;
    g=r=1;
    for(;g==1;){
      x=y;
      for(;4*k<3*r;k++) y=f(y);
      for(;k<r&&g==1;){
        ys=y;
        q=1;
        for(int i=0;i<min(m,r-k);i++){
          y=f(y);
          d=x>y?x-y:y-x;
          q=(__uint128_t(q)*d+__uint128_t(q*d*imod)*mod)>>64;
          if(q>=mod) q-=mod;
        }
        g=gcd(q,n);
        k+=m;
      }
      k=r;
      r*=2;
    }
    if(g==n){
      g=1;
      y=ys;
      for(;g==1;){
        y=f(y);
        g=gcd(x>y?x-y:y-x,n);
      }
    }
    if(g==n) continue;
    else if(IsPrime(g)) return g;
    else if(IsPrime(n/g)) return n/g;
    else return FindPrimeFactor(g);
  }
}
vector<long long> Factorize(long long n){
  vector<long long> ret;
  long long p;
  for(;!IsPrime(n)&&n>1;){
    p=FindPrimeFactor(n);
    for(;n%p==0;){
      n/=p;
      ret.push_back(p);
    }
  }
  if(n>1) ret.push_back(n);
  sort(ret.begin(),ret.end());
  return ret;
}
void solve(){
  long long l;
  cin>>l;
  auto F=Factorize(l);
  long long p=F.back();
  if(p==2){
    long long r=l/4;
    cout<<r*3<<" "<<r*4<<" "<<r*5<<endl;
    return;
  }
  long long r=l/p;
  cout<<r*p<<" "<<r*(p*p-1)/2<<" "<<r*(p*p+1)/2<<endl;
}
int main(){
  int t;
  cin>>t;
  while(t--) solve();
}
0