結果

問題 No.3248 構築問題
ユーザー daiota
提出日時 2025-08-30 13:36:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 864 bytes
コンパイル時間 1,741 ms
コンパイル使用メモリ 169,472 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-08-30 13:36:10
合計ジャッジ時間 1,859 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(ll i=0;i<ll(n);i++)




vector<ll> div(ll n){
	vector<ll> d;
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			d.push_back(i);
			if(i!=n/i) d.push_back(n/i);
		}
	}

	return d;
}


map<ll,ll> f(ll n){
  map<ll,ll> p;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      p[i]++;
      n/=i;
    }
  }

  if(n!=1) p[n]=1;

  return p;
}





int main(void){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	ll i,j;






	ll n,x;
	cin >> n >> x;


	vector<ll> v=div(n);

	REP(i,v.size()){

		ll N=n/v[i];

		map<ll,ll> m=f(N);

		bool g=true;
		ll c=1;
		for(auto a:m){
			c*=a.first;
			if((a.second)%x!=0){
				g=false;
				break;
			}
		}

		if(g && c!=v[i]){
			cout << "Yes" << endl;
			return 0;
		}

	}



	cout << "No" << endl;





	return 0;

}
0