結果

問題 No.2682 Visible Divisible
ユーザー pitP
提出日時 2024-03-21 02:16:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,073 bytes
コンパイル時間 4,642 ms
コンパイル使用メモリ 262,148 KB
最終ジャッジ日時 2025-02-20 10:28:44
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘long long int find_prime_factor(long long int)’:
main.cpp:130:1: warning: control reaches end of non-void function [-Wreturn-type]
  130 | }
      | ^

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }
istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }
istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }
ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }
typedef long long ll;
typedef vector<vector<int>> Graph;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)
#define rep(i,n) for (int i = 0;i < (int)(n); i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define my_sort(x) sort(x.begin(), x.end())
#define my_max(x) *max_element(all(x))
#define my_min(x) *min_element(all(x))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<62) - 1;
const int MOD = 998244353;
const int MOD2 = 1e9+7;
const double PI = acos(-1);
vector<int> di = {1,0,-1,0};
vector<int> dj = {0,1,0,-1};
#ifdef LOCAL
# include <debug_print.hpp>
# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
# define debug(...) (static_cast<void>(0))
#endif
// A ^ N M
template<class T> T pow_mod(T A, T N, T M) {
T res = 1 % M;
A %= M;
while (N) {
if (N & 1) res = (res * A) % M;
A = (A * A) % M;
N >>= 1;
}
return res;
}
// Miller-Rabin
bool Miller_Rabin(long long N) {
if (N <= 1) return false;
if (N == 2) return true;
if (N % 2 == 0) return false;
vector<long long> A = {2, 325, 9375, 28178, 450775,
9780504, 1795265022};
long long s = 0, d = N - 1;
while (d % 2 == 0) {
++s;
d >>= 1;
}
for (auto a : A) {
if (a % N == 0) return true;
long long t, x = pow_mod<__int128_t>(a, d, N);
if (x != 1) {
for (t = 0; t < s; ++t) {
if (x == N - 1) break;
x = __int128_t(x) * x % N;
}
if (t == s) return false;
}
}
return true;
}
// https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a#%E3%81%AF%E3%81%98%E3%82%81%E3%81%AB
long long _inner_random(long long a, long long c, long long mod){
return (((a % mod) * a) % mod + c) % mod;
};
// O(N^0.25 * logN)
long long find_prime_factor(long long N){
if((N % 2) == 0) return 2;
long long m = (long long)pow(N, 0.125) + 1;
for(long long c = 1; c < N; c++){
long long y = 0;
long long g = 1;
long long q = 1;
long long r = 1;
long long k = 0;
long long x, ys;
while(g == 1){
x = y;
while(k < (3 * r / 4)){
y = _inner_random(y, c, N);
k++;
}
while(k < r && g == 1){
ys = y;
for(int i = 0; i < min(m, r - k); i++){
y = _inner_random(y, c, N);
q = __int128_t(q) * abs(x - y) % N;
}
g = __gcd(q, N);
k += m;
}
k = r;
r *= 2;
}
if(g == N){
g = 1;
y = ys;
while(g == 1){
y = _inner_random(y, c, N);
g = __gcd(abs(x - y), N);
}
}
if(g == N) continue;
if(Miller_Rabin(g)) return g;
else if(Miller_Rabin(N/g)) return N/g;
else return find_prime_factor(g);
}
}
// (p, cnt)
unordered_map<ll,ll> Pollard_rho(long long N){
unordered_map<ll,ll> res;
while(!Miller_Rabin(N) && N > 1){
long long p = find_prime_factor(N);
long long s = 0;
while((N % p) == 0){
N /= p;
s++;
}
res[p] = s;
}
if(N > 1){
res[N] = 1;
}
return res;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
int N; cin >> N;
ll K; cin >> K;
vector<ll> A(N);
rep(i,N) cin >> A[i];
unordered_map<ll,ll> facts = Pollard_rho(K);
unordered_map<ll,ll> mp;
vector<ll> p;
for(auto itr = facts.begin(); itr != facts.end(); itr++){
p.push_back(itr->first);
mp[itr->first] = 0;
}
rep(i,N){
for(auto &v: p){
ll cnt = 0;
while((A[i] % v) == 0){
A[i] /= v;
cnt++;
}
mp[v] = max(mp[v], cnt);
}
}
for(auto &v : p){
if(mp[v] < facts[v]){
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0