結果

問題 No.2262 Fractions
ユーザー umezo
提出日時 2023-04-07 22:53:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,368 bytes
コンパイル時間 2,120 ms
コンパイル使用メモリ 195,372 KB
最終ジャッジ日時 2025-02-12 02:16:37
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1
other AC * 17 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
 
#include<bits/stdc++.h>
using namespace std;

ll eulerPhi(ll n) {
    if (n == 0){
        return (0);
    }
    ll ans = n;
    for(ll x = 2; x * x <= n; ++x){
        if (n % x == 0) {
            ans -= ans / x;
            while (n % x == 0){
                n /= x;
            }
        }
    }
    if (n > 1){
        ans -= ans / n;
    }
    return (ans);
}

int MAX=300300;

int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  vector<ll> euler(MAX);  
  for(int i = 1; i <= MAX; i++) euler[i] = eulerPhi(i);
  for(int i = 1; i <= MAX; i++) euler[i] += euler[i - 1];
  
  int t;
  cin>>t;
  while(t--){
    ll n,k;
    cin>>n>>k;
    ll a=euler[n];
    if(k>=2*a){
      cout<<-1<<'\n';
      continue;
    }
    if(k==a){
      cout<<"1/1\n";
      continue;
    }
    int c=0;
    if(k>a){
      k=2*a-k;
      c=1;
    }
    
    ll idx=0;
    auto make=[&](auto make,ll a1,ll a2,ll b1,ll b2)->void{
      ll c1 = a1 + b1, c2 = a2 + b2;
      if (idx > k) return;
      if (c2 > n) return;
      make(make,a1, a2, c1, c2);
      idx++;
	  if(idx == k){
		if(c==0) cout<<c1<<'/'<<c2<<"\n";
        else cout<<c2<<'/'<<c1<<"\n";
		return;
      }
	  make(make,c1, c2, b1, b2);
    };
    
    make(make,0,1,1,1);
  }
    
  return 0;
}
0