結果
| 問題 | No.442 和と積 |
| ユーザー |
 firiexp
|
| 提出日時 | 2019-03-02 15:41:51 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 4,037 bytes |
| コンパイル時間 | 830 ms |
| コンパイル使用メモリ | 106,280 KB |
| 最終ジャッジ日時 | 2024-04-27 02:48:58 |
| 合計ジャッジ時間 | 1,213 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:15:39: error: '::numeric_limits' has not been declared
15 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
| ^~~~~~~~~~~~~~
main.cpp:15:55: error: expected primary-expression before '>' token
15 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
| ^
main.cpp:15:61: error: no matching function for call to 'max()'
15 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
| ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
from main.cpp:1:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
main.cpp:15:61: note: candidate expects 2 arguments, 0 provided
15 | template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
| ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:300:5: note: candidate: 'templat
ソースコード
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
static const int MOD = 1000000007;
using ll = int64_t;
using namespace std;
template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;
#include <random>
template< class T>
T pow_ (T x, uint64_t n, uint64_t M){
T u = 1;
if(n > 0){
u = pow_(x, n/2, M);
if (n % 2 == 0) u = (u*u) % M;
else u = (((u * u)% M) * x) % M;
}
return u;
};
bool suspect(__uint128_t a, uint64_t s, uint64_t d, uint64_t n){
__uint128_t x = pow_(a, d, n);
if (x == 1) return true;
for (int r = 0; r < s; ++r) {
if(x == n-1) return true;
x = x * x % n;
}
return false;
}
template<class T>
bool miller_rabin(T m){
uint64_t n = m;
if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
uint64_t d = n - 1, s = 0;
while (!(d&1)) {++s; d >>= 1;}
vector<uint64_t> v = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
if(n <= 4759123141LL) v = {2, 7, 61};
for (auto &&p : v) {
if(p >= n) break;
if(!suspect(p, s, d, n)) return false;
}
return true;
}
vector<int> get_prime(int n) {
if(n <= 1) return vector<int>{};
vector<bool> prime(static_cast<unsigned int>(n + 1), true);
vector<int> res;
prime[0] = false; prime[1] = false;
for(int i = 2; i * i <= n; i++){
if(prime[i]) for(int j = i << 1; j <= n; j += i) prime[j] = false;
}
for (int i = 2; i <= n; ++i) {
if(prime[i]) res.emplace_back(i);
}
return res;
}
const auto p = get_prime(100000);
random_device rng;
template<class T>
T pollard_rho2(T n) {
uniform_int_distribution<T> ra(1, n-1);
while(true){
T c = ra(rng), g = 1, r = 1, y = ra(rng),m = 1900,
ys = 0, q = 1, xx = 0;
while(c == n-2) c = ra(rng);
while(g == 1){
xx = y;
for (int i = 1; i <= r; ++i) {
y = static_cast<T>(((__uint128_t)y * y) % n);
y = static_cast<T>((__uint128_t)y + c) % n;
}
T k = 0; g = 1;
while(k < r && g == 1){
for (int i = 1; i <= (m > (r-k) ? (r-k) : m); ++i) {
ys = y;
y = static_cast<T>(((__uint128_t)y * y) % n);
y = static_cast<T>((__uint128_t)y + c) % n;
q = static_cast<T>(((__uint128_t)q * (xx > y ? xx - y : y - xx)) % n);
}
g = __gcd(q, n);
k += m;
}
r *= 2;
}
if(g == n) g = 1;
while (g == 1){
ys = static_cast<T>(((__uint128_t)ys * ys) % n);
ys = static_cast<T>((__uint128_t)ys + c) % n;
g = __gcd(xx > ys ? xx - ys : ys - xx, n);
}
if (g != n && miller_rabin(g)) return g;
}
}
template<class T>
vector<T> prime_factor(T n, int d = 0){
vector<T> a, res;
if(!d) for (auto &&i : p) {
while (n % i == 0){
res.emplace_back(i);
n /= i;
}
}
while(n != 1){
if(miller_rabin(n)){
a.emplace_back(n);
break;
}
T x = pollard_rho2(n);
n /= x;
a.emplace_back(x);
}
for (auto &&i : a) {
if (miller_rabin(i)) {
res.emplace_back(i);
} else {
vector<T> b = prime_factor(i, d + 1);
for (auto &&j : b) res.emplace_back(j);
}
}
return res;
}
int main() {
ll a, b;
cin >> a >> b;
vector<ll> p = prime_factor(a), q = prime_factor(b), r = prime_factor(a+b);
map<ll, int> m1, m2;
for (auto &&i : p) m1[i]++;
for (auto &&i : q) m1[i]++;
for (auto &&i : r) m2[i]++;
ll ans = 1;
for (auto &&i : m1) {
for (int j = 0; j < min(i.second, m2[i.first]); ++j) {
ans *= i.first;
}
}
cout << ans << "\n";
return 0;
}