QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#514083 | #9167. Coprime Array | ucup-team1134# | AC ✓ | 1ms | 3820kb | C++23 | 5.8kb | 2024-08-10 21:40:45 | 2024-10-14 07:52:26 |
Judging History
answer
#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;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<ll> solve(ll S,ll X){
if(gcd(S,X)==1) return {S};
if(gcd(S,X)%2==0||X&1){
for(ll d=0;;d++){
ll a=S/2+d,b=S-a;
if(gcd(a,X)==1&&gcd(b,X)==1){
return {a,b};
}
}
}
if(gcd(S+2,X)==1){
return {S+2,-1,-1};
}else if(gcd(S-2,X)==1){
return {S-2,1,1};
}else{
while(1){
ll a=rng()%mod-500000000;
if(gcd(abs(a),X)>1) continue;
ll b=rng()%mod-500000000;
if(gcd(abs(b),X)>1) continue;
ll c=S-a-b;
if(gcd(abs(c),X)>1) continue;
return {a,b,c};
}
}
return {};
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
ll S,X;cin>>S>>X;
auto res=solve(S,X);
cout<<si(res)<<"\n";
for(ll x:res) cout<<x<<" ";
cout<<endl;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3692kb
input:
9 6
output:
3 11 -1 -1
result:
ok Correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
14 34
output:
2 7 7
result:
ok Correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1000000000 223092870
output:
2 500000021 499999979
result:
ok Correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2 1000000000
output:
2 1 1
result:
ok Correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
649557664 933437700
output:
2 324778841 324778823
result:
ok Correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
33396678 777360870
output:
2 16698349 16698329
result:
ok Correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
48205845 903124530
output:
3 48205847 -1 -1
result:
ok Correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
251037078 505905400
output:
2 125518539 125518539
result:
ok Correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
30022920 172746860
output:
2 15011467 15011453
result:
ok Correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
63639298 808058790
output:
2 31819649 31819649
result:
ok Correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
76579017 362768406
output:
3 76579015 1 1
result:
ok Correct
Test #12:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
40423669 121437778
output:
3 40423671 -1 -1
result:
ok Correct
Test #13:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
449277309 720915195
output:
2 224638658 224638651
result:
ok Correct
Test #14:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
81665969 919836918
output:
3 81665971 -1 -1
result:
ok Correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
470578680 280387800
output:
2 235289357 235289323
result:
ok Correct
Test #16:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
58450340 803305503
output:
2 29225176 29225164
result:
ok Correct
Test #17:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
125896113 323676210
output:
3 -45076843 -31916101 202889057
result:
ok Correct
Test #18:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
381905348 434752500
output:
2 190952689 190952659
result:
ok Correct
Test #19:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
78916498 653897673
output:
1 78916498
result:
ok Correct
Test #20:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
35787885 270845190
output:
3 35787883 1 1
result:
ok Correct
Extra Test:
score: 0
Extra Test Passed