fork(23) download 
  1. #include <algorithm>
  2. #include <iostream>
  3.  
  4. constexpr unsigned exponent        = 31;
  5. constexpr unsigned two_to_exponent = 1u << exponent;
  6.  
  7. unsigned solve_p_even(unsigned n,unsigned s, unsigned p, unsigned q) {
  8.  
  9.     if (p == 0) {
  10.         if (s == q)
  11.             return 1;
  12.         return 2;
  13.     }
  14.  
  15.     if (s == 0 && q == 0)
  16.         return 1;
  17.  
  18.     unsigned a1_minus_a0 = (p - 1) * s + q;
  19.     unsigned numerator   = exponent - __builtin_popcount((a1_minus_a0 & -a1_minus_a0) - 1);
  20.     unsigned denominator = __builtin_popcount((p & -p) - 1);
  21.     unsigned m           = numerator / denominator + (numerator % denominator == 0 ? 1 : 2);
  22.     return std::min(m , n);
  23. }
  24.  
  25. unsigned solve_p_odd(unsigned n,unsigned s, unsigned p, unsigned q) {
  26.  
  27.     if (p == 1)
  28.         return q == 0 ? 1 : std::min(n, two_to_exponent / (q & -q));
  29.  
  30.     if (s == 0 && q == 0)
  31.         return 1;
  32.  
  33.     unsigned           m           = 1;
  34.     unsigned long long p_minus_1   = p - 1;
  35.     unsigned long long a1_minus_a0 = p_minus_1 * s + q;
  36.     unsigned long long p_to_m      = p;
  37.     unsigned long long mask        = (two_to_exponent *
  38.         (p_minus_1 & -p_minus_1) / (a1_minus_a0 & -a1_minus_a0)) - 1;
  39.  
  40.     while (m < n && (p_to_m & mask) != 1) {
  41.         p_to_m = p_to_m * p_to_m;
  42.         m      = m * 2;
  43.     }
  44.  
  45.     return std::min(m, n);
  46. }
  47.  
  48. unsigned solve(unsigned n, unsigned s, unsigned p, unsigned q) {
  49.     if (p % 2 == 0)
  50.         return solve_p_even(n, s, p, q);
  51.     return solve_p_odd(n, s, p, q);
  52. }
  53.  
  54. int main() {
  55.     unsigned n, s, p, q;
  56.     std::cin >> n >> s >> p >> q;
  57.     std::cout << solve(n, s, p, q);
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0s 3416KB
comments (?)
stdin 
100000000 1 3 1
stdout 
100000000
https://ideone.com/gFQgqT
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!