pub fn prime_factors(n: u64) -> Vec<(u64, u32)>Examples found in repository?
More examples
crates/competitive/src/math/prime_factors.rs (line 83)
81pub fn divisors(n: u64) -> Vec<u64> {
82 let mut d = vec![1u64];
83 for (p, c) in prime_factors(n) {
84 let k = d.len();
85 let mut acc = 1;
86 for _ in 0..c {
87 acc *= p;
88 for i in 0..k {
89 d.push(d[i] * acc);
90 }
91 }
92 }
93 d.sort_unstable();
94 d
95}crates/competitive/src/math/factorial.rs (line 84)
82 fn default() -> Self {
83 let m = M::mod_into();
84 let pf = prime_factors(m as _);
85 assert!(pf.len() <= 1);
86 let p = pf[0].0 as u32;
87 let c = pf[0].1;
88 let mut fact = vec![MInt::one(); m];
89 let mut inv_fact = vec![MInt::one(); m];
90 let mut pow = vec![MInt::one(); c as usize];
91 for i in 2..m {
92 fact[i] = fact[i - 1]
93 * if i as u32 % p != 0 {
94 MInt::from(i)
95 } else {
96 MInt::one()
97 };
98 }
99 inv_fact[m - 1] = fact[m - 1].inv();
100 for i in (3..m).rev() {
101 inv_fact[i - 1] = inv_fact[i]
102 * if i as u32 % p != 0 {
103 MInt::from(i)
104 } else {
105 MInt::one()
106 };
107 }
108 for i in 1..c as usize {
109 pow[i] = pow[i - 1] * MInt::from(p as usize);
110 }
111 Self {
112 p,
113 c,
114 fact,
115 inv_fact,
116 pow,
117 }
118 }crates/competitive/src/math/discrete_logarithm.rs (line 432)
379fn discrete_logarithm_prime_power(a: u64, b: u64, p: u64, e: u32) -> Option<(u64, u64)> {
380 assert_ne!(p, 0);
381 assert_ne!(e, 0);
382 let n = p.pow(e);
383 assert!(a < n);
384 assert!(b < n);
385 assert_eq!(gcd(a, p), 1);
386 if p == 1 {
387 return Some((0, 1));
388 }
389 if a == 0 {
390 return if b == 0 { Some((1, 1)) } else { None };
391 }
392 if b == 0 {
393 return None;
394 }
395 if e == 1 {
396 return IC.with(|ic| unsafe { &mut *ic.get() }.discrete_logarithm(a, b, p));
397 }
398 let br = BarrettReduction::<u128>::new(n as _);
399 if p == 2 {
400 if e >= 3 {
401 if a % 4 == 1 && b % 4 != 1 {
402 return None;
403 }
404 let aa = if a % 4 == 1 { a } else { n - a };
405 let bb = if b % 4 == 1 { b } else { n - b };
406 let g = 5;
407 let ord = n / 4;
408 let x = pohlig_hellman_prime_power_order(g, aa, n, p, e - 2)?;
409 let y = pohlig_hellman_prime_power_order(g, bb, n, p, e - 2)?;
410 let t = solve_linear_congruence(x, y, ord)?;
411 match (a % 4 == 1, b % 4 == 1) {
412 (true, true) => Some(t),
413 (false, true) if t.0 % 2 == 0 => Some((t.0, lcm(t.1, 2))),
414 (false, false) if t.0 % 2 == 1 => Some((t.0, lcm(t.1, 2))),
415 (false, false) if a == b => Some((1, lcm(t.1, 2))),
416 _ => None,
417 }
418 } else if a == 1 {
419 if b == 1 { Some((0, 1)) } else { None }
420 } else {
421 assert_eq!(a, 3);
422 if b == 1 {
423 Some((0, 2))
424 } else if b == 3 {
425 Some((1, 2))
426 } else {
427 None
428 }
429 }
430 } else {
431 let ord = n - n / p;
432 let pf_ord = prime_factors(ord);
433 let g = (2..)
434 .find(|&g| check_primitive_root(g, ord, &br, &pf_ord))
435 .unwrap();
436 let mut pf_p = prime_factors(p - 1);
437 pf_p.push((p, e - 1));
438 let mut abm = vec![];
439 for (q, c) in pf_p {
440 let m = q.pow(c);
441 let d = ord / m;
442 let gg = pow(g, d, &br);
443 let aa = pow(a, d, &br);
444 let bb = pow(b, d, &br);
445 let x = pohlig_hellman_prime_power_order(gg, aa, n, q, c)?;
446 let y = pohlig_hellman_prime_power_order(gg, bb, n, q, c)?;
447 abm.push((x, y, m));
448 }
449 solve_linear_congruences(abm)
450 }
451}
452
453/// a^x ≡ b (mod n)
454pub fn discrete_logarithm(a: u64, b: u64, n: u64) -> Option<u64> {
455 let a = a % n;
456 let b = b % n;
457 let d = 2.max(64 - n.leading_zeros() as u64);
458 let mut pw = 1 % n;
459 for i in 0..d {
460 if pw == b {
461 return Some(i);
462 }
463 pw = (pw as u128 * a as u128 % n as u128) as u64;
464 }
465 let g = gcd(pw, n);
466 if b % g != 0 {
467 return None;
468 }
469 let n = n / g;
470 let b = (b as u128 * modinv(pw, n) as u128 % n as u128) as u64;
471 let pf = prime_factors(n);
472 let mut abm = vec![];
473 for (p, e) in pf {
474 let q = p.pow(e);
475 let x = discrete_logarithm_prime_power(a % q, b % q, p, e)?;
476 abm.push((1, x.0, x.1));
477 }
478 solve_linear_congruences(abm).map(|x| x.0 + d)
479}