結果
| 問題 |
No.2798 Multiple Chain
|
| コンテスト | |
| ユーザー |
 Rubikun
|
| 提出日時 | 2024-06-28 21:59:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,931 ms / 2,000 ms |
| コード長 | 5,818 bytes |
| コンパイル時間 | 2,602 ms |
| コンパイル使用メモリ | 214,308 KB |
| 最終ジャッジ日時 | 2025-02-22 01:05:58 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 51 |
コンパイルメッセージ
main.cpp:29:9: warning: #pragma once in main file
29 | #pragma once
| ^~~~
main.cpp:82:9: warning: #pragma once in main file
82 | #pragma once
| ^~~~
main.cpp:94:9: warning: #pragma once in main file
94 | #pragma once
| ^~~~
ソースコード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;
/**
* Author: chilli, Ramchandra Apte, Noam527, Simon Lindholm
* Date: 2019-04-24
* License: CC0
* Source: https://github.com/RamchandraApte/OmniTemplate/blob/master/modulo.hpp…
* Description: Calculate $a\cdot b\bmod c$ (or $a^b \bmod c$) for $0 \le a, b \le c \le 7.2\cdot 10^{18}$.
* Time: O(1) for \texttt{modmul}, O(\log b) for \texttt{modpow}
* Status: stress-tested, proven correct
* Details:
* This runs ~2x faster than the naive (__int128_t)a * b % M.
* A proof of correctness is in doc/modmul-proof.tex. An earlier version of the proof,
* from when the code used a * b / (long double)M, is in doc/modmul-proof.md.
* The proof assumes that long doubles are implemented as x87 80-bit floats; if they
* are 64-bit, as on e.g. MSVC, the implementation is only valid for
* $0 \le a, b \le c < 2^{52} \approx 4.5 \cdot 10^{15}$.
*/
#pragma once
typedef unsigned long long ull;
ull modmul(ull a, ull b, ull M) {
ll ret = a * b - M * ull(1.L / M * a * b);
return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull modpow(ull b, ull e, ull mod) {
ull ans = 1;
for (; e; b = modmul(b, b, mod), e /= 2)
if (e & 1) ans = modmul(ans, b, mod);
return ans;
}
/**
* Author: chilli, SJTU, pajenegod
* Date: 2020-03-04
* License: CC0
* Source: own
* Description: Pollard-rho randomized factorization algorithm. Returns prime
* factors of a number, in arbitrary order (e.g. 2299 -> \{11, 19, 11\}).
* Time: $O(n^{1/4})$, less for numbers with small factors.
* Status: stress-tested
*
* Details: This implementation uses the improvement described here
* (https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#Variants…), where
* one can accumulate gcd calls by some factor (40 chosen here through
* exhaustive testing). This improves performance by approximately 6-10x
* depending on the inputs and speed of gcd. Benchmark found here:
* (https://ideone.com/nGGD9T)
*
* GCD can be improved by a factor of 1.75x using Binary GCD
* (https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/…).
* However, with the gcd accumulation the bottleneck moves from the gcd calls
* to the modmul. As GCD only constitutes ~12% of runtime, speeding it up
* doesn't matter so much.
*
* This code can probably be sped up by using a faster mod mul - potentially
* montgomery reduction on 128 bit integers.
* Alternatively, one can use a quadratic sieve for an asymptotic improvement,
* which starts being faster in practice around 1e13.
*
* Brent's cycle finding algorithm was tested, but doesn't reduce modmul calls
* significantly.
*
* Subtle implementation notes:
* - we operate on residues in [1, n]; modmul can be proven to work for those
* - prd starts off as 2 to handle the case n = 4; it's harmless for other n
* since we're guaranteed that n > 2. (Pollard rho has problems with prime
* powers in general, but all larger ones happen to work.)
* - t starts off as 30 to make the first gcd check come earlier, as an
* optimization for small numbers.
*/
#pragma once
/**
* Author: chilli, c1729, Simon Lindholm
* Date: 2019-03-28
* License: CC0
* Source: Wikipedia, https://miller-rabin.appspot.com
* Description: Deterministic Miller-Rabin primality test.
* Guaranteed to work for numbers up to $7 \cdot 10^{18}$; for larger numbers, use Python and extend A randomly.
* Time: 7 times the complexity of $a^b \mod c$.
* Status: Stress-tested
*/
#pragma once
bool isPrime(ull n) {
if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
s = __builtin_ctzll(n-1), d = n >> s;
for (ull a : A) { // ^ count trailing zeroes
ull p = modpow(a%n, d, n), i = s;
while (p != 1 && p != n - 1 && a % n && i--)
p = modmul(p, p, n);
if (p != n-1 && i != s) return 0;
}
return 1;
}
ull pollard(ull n) {
auto f = [n](ull x) { return modmul(x, x, n) + 1; };
ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
while (t++ % 40 || __gcd(prd, n) == 1) {
if (x == y) x = ++i, y = f(x);
if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;
x = f(x), y = f(f(y));
}
return __gcd(prd, n);
}
vector<ull> factor(ull n) {
if (n == 1) return {};
if (isPrime(n)) return {n};
ull x = pollard(n);
auto l = factor(x), r = factor(n / x);
l.insert(l.end(), all(r));
return l;
}
ll ans;
vector<pair<ll,ll>> S;
vector<ll> T;
void DFS(int u,ll x){
if(u==si(S)){
T.push_back(x);
return;
}
for(int q=0;q<=S[u].se;q++){
DFS(u+1,x);
x*=S[u].fi;
}
}
void solve(ll la,ll rem){
if(rem==1){
ans++;
return;
}
if(la>rem) return;
if(la==rem){
ans++;
return;
}
if(rem%la) return;
if((rem/la)%la){
if(rem%la==0) ans++;
return;
}
auto it=lower_bound(all(T),la);
while(it!=T.end()){
ll x=*it;
if(x%la==0&&rem%x==0){
solve(x,rem/x);
}
if(x>rem) return;
it++;
}
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
ll N;cin>>N;
auto fa=factor(N);
//return 0;
map<ll,ll> MA;
for(ll x:fa) MA[x]++;
for(auto [a,b]:MA) S.push_back(mp(a,b));
DFS(0,1);
sort(all(T));
for(ll x:T){
if(x==1) continue;
solve(x,N/x);
}
cout<<ans<<endl;
}