Submission #1368458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368458		neelamneelam19	Hack (APIO25_hack)	C++20	Compilation error	0 ms	0 KiB

hack

#include <bits/stdc++.h>
using namespace std;

long long collisions(vector<long long> x);

bool divides(long long d) {
    return collisions({d, 2*d, 3*d}) == 3;
}

int hack() {
    // Sieve primes up to 500000
    const int MAXN = 10000001;
    vector<bool> is_prime(MAXN, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < MAXN; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (long long j = (long long)i*i; j < MAXN; j += i)
                is_prime[j] = false;
        }
    }

    long long n = 1; // our reconstructed answer

    for (int p : primes) {
        if ((long long)p > 500000 / n) break; // p*n > 500000, p can't be a new factor
        
        if (!divides((long long)p)) continue;

        // p divides the true n. Find the highest power.
        long long pk = p;
        while ((long long)pk * p <= 500000 / n && divides(pk * p))
            pk *= p;

        n *= pk;
    }

    // Check for one remaining large prime factor
    // true_n / n is either 1 or a prime > current largest tested prime
    // Since we tested ALL primes up to 500000/n, if none divide, remainder=1.
    // But if n=1, we need to find the prime n directly via binary search on primes list.
    // Actually the loop handles it: if n=1, we test p=2,3,5,... until p > 500000.
    // If n is prime, we'll detect it when p == n (and n*p <= 500000 is false if n > 707).
    // FIX: We need to also test large primes (> 500000/n) as potential sole factors.
    
    // After loop, if n == 1, do a separate binary search:
    if (n == 1) {
        // n_true is a prime itself. Binary search in primes list.
        int lo = 0, hi = (int)primes.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (divides(primes[mid])) hi = mid;
            else lo = mid + 1;
        }
        n = primes[lo];
    }

    return (int)n;
}

Compilation message (stderr)

hack.cpp: In function 'int hack()':
hack.cpp:29:14: error: reference to 'divides' is ambiguous
   29 |         if (!divides((long long)p)) continue;
      |              ^~~~~~~
In file included from /usr/include/c++/13/string:49,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from hack.cpp:1:
/usr/include/c++/13/bits/stl_function.h:169:12: note: candidates are: 'template<class _Tp> struct std::divides'
  169 |     struct divides;
      |            ^~~~~~~
hack.cpp:6:6: note:                 'bool divides(long long int)'
    6 | bool divides(long long d) {
      |      ^~~~~~~
hack.cpp:33:51: error: reference to 'divides' is ambiguous
   33 |         while ((long long)pk * p <= 500000 / n && divides(pk * p))
      |                                                   ^~~~~~~
/usr/include/c++/13/bits/stl_function.h:169:12: note: candidates are: 'template<class _Tp> struct std::divides'
  169 |     struct divides;
      |            ^~~~~~~
hack.cpp:6:6: note:                 'bool divides(long long int)'
    6 | bool divides(long long d) {
      |      ^~~~~~~
hack.cpp:53:17: error: reference to 'divides' is ambiguous
   53 |             if (divides(primes[mid])) hi = mid;
      |                 ^~~~~~~
/usr/include/c++/13/bits/stl_function.h:169:12: note: candidates are: 'template<class _Tp> struct std::divides'
  169 |     struct divides;
      |            ^~~~~~~
hack.cpp:6:6: note:                 'bool divides(long long int)'
    6 | bool divides(long long d) {
      |      ^~~~~~~