Last active
July 16, 2025 16:30
-
-
Save zyr17/1ac2fccc070784a3900406155e285d76 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| // 设置栈大小为 64MB (Windows) | |
| #ifdef _WIN32 | |
| #pragma comment(linker, "/STACK:67108864") | |
| #endif | |
| #define DELTA 128 * 100000 | |
| #define MAX 10000000000000LL | |
| // int vecs[22][22]; | |
| const int vecs[10][15] = { | |
| {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | |
| {1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2}, | |
| {2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4}, | |
| {3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6}, | |
| {4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1}, | |
| {5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3}, | |
| {6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5}, | |
| {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | |
| {1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2}, | |
| {2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4} | |
| }; | |
| int res[DELTA] = {0}; | |
| int res1[DELTA / 128 + 1] = {0}; | |
| inline bool check_zero(int n) { | |
| if (n < 0) n += 7; | |
| if (n < 0) n += 7; | |
| if (n >= 7) n -= 7; | |
| if (n >= 7) n -= 7; | |
| return n == 0; | |
| } | |
| bool check_has_7(__int128 n) { | |
| int nn = n; | |
| // std::cout << "Checking: " << nn; | |
| std::vector<__int128> vec; | |
| int ans = n % 7; | |
| while (n) { | |
| vec.push_back(n % 10); | |
| n /= 10; | |
| } | |
| if (ans == 0) { | |
| // std::cout << " -> " << nn << " is already divisible by 7" << std::endl; | |
| return false; | |
| } | |
| int vs = vec.size(); | |
| for (int i = 0; i < vs; i ++ ) { | |
| for (int j = 0; j < i; j ++ ) { | |
| if (i == vs - 1 && vec[j] == 0) continue; | |
| int newans = ans; | |
| newans -= vecs[vec[i]][i] + vecs[vec[j]][j]; | |
| newans += vecs[vec[i]][j] + vecs[vec[j]][i]; | |
| if (check_zero(newans)) { | |
| // std::cout << " -> " << nn << " can be formed by " << vec[i] << " and " << vec[j] << std::endl; | |
| // std::cout << ans << " - " << vecs[vec[i]][i] << " - " << vecs[vec[j]][j] | |
| // << " + " << vecs[vec[i]][j] << " + " << vecs[vec[j]][i] | |
| // << " = " << newans << std::endl; | |
| return false; | |
| } | |
| } | |
| } | |
| // std::cout << " -> " << ans << std::endl; | |
| return true; | |
| } | |
| void P954() { | |
| // for (int i = 0; i < 10; i ++ ) { | |
| // vecs[i][0] = i % 7; | |
| // for (int j = 1; j < 15; j ++ ) { | |
| // vecs[i][j] = (vecs[i][j - 1] * 10) % 7; | |
| // } | |
| // } | |
| // // output vecs in c++ style to make it const | |
| // std::cout << "const int vecs[10][15] = {" << std::endl; | |
| // for (int i = 0; i < 10; i ++ ) { | |
| // std::cout << " {"; | |
| // for (int j = 0; j < 15; j ++ ) { | |
| // std::cout << vecs[i][j]; | |
| // if (j < 14) std::cout << ", "; | |
| // } | |
| // std::cout << "}"; | |
| // if (i < 9) std::cout << ","; | |
| // std::cout << std::endl; | |
| // } | |
| std::cout << "solving P954..." << std::endl; | |
| __int128 restot = 0; | |
| for (long long i = MAX - 1; i > 0; i -= DELTA) { | |
| std::cout << "Checking: " << i << ", current total: " << (long long)restot << std::endl; | |
| memset(res, 0, sizeof(res)); | |
| #pragma omp parallel for | |
| for (int j = 0; j < DELTA; j ++ ) { | |
| res[j] = check_has_7(i - j); | |
| } | |
| for (__int128 j = i; j < DELTA; j ++ ) { | |
| res[j] = 0; | |
| } | |
| memset(res1, 0, sizeof(res1)); | |
| #pragma omp parallel for | |
| for (int k = 0; k < DELTA / 128; k++) { | |
| int sum = 0; | |
| for (int j = k * 128; j < (k + 1) * 128; j++) { | |
| sum += res[j]; | |
| } | |
| res1[k] = sum; | |
| } | |
| for (int j = 0; j < DELTA / 128 + 1; j ++ ) { | |
| restot += res1[j]; | |
| } | |
| } | |
| std::cout << (long long)restot << std::endl; | |
| } | |
| void P001() { | |
| bool is[11111] = {0}; | |
| for (int i = 0; i < 11111; i += 3) { | |
| is[i] = true; | |
| } | |
| for (int i = 0; i < 11111; i += 5) { | |
| is[i] = true; | |
| } | |
| long long res = 0; | |
| for (int i = 0; i < 1000; i ++ ) { | |
| if (is[i]) { | |
| res += i; | |
| } | |
| } | |
| std::cout << res << std::endl; | |
| } | |
| int primecount(int N, std::vector<int> &primes) { | |
| std::vector<bool> prime(N + 1, true); | |
| prime[0] = prime[1] = false; | |
| for (int i = 2; i <= N; i ++ ) { | |
| if (prime[i]) { | |
| for (int j = i * 2; j <= N; j += i) { | |
| prime[j] = false; | |
| } | |
| } | |
| } | |
| int count = 0; | |
| for (int i = 0; i < N; i ++ ) { | |
| if (prime[i]) { | |
| count++; | |
| primes.push_back(i); | |
| } | |
| } | |
| return count; | |
| } | |
| __int128 dfs_953_old(const std::vector<int> &primes, int idx, int xr, __int128 pd, __int128 N) { | |
| // std::cout << "dfs called with idx: " << idx << ", xr: " << xr << ", pd: " << pd << std::endl; | |
| if (pd > N) return 0; | |
| __int128 remain = N / pd + 1; | |
| if (xr > primes[idx] * 2) return 0; | |
| __int128 res = 0; | |
| if (xr == 0) { | |
| res = pd; | |
| } | |
| // if (xr == 0) std::cout << "Found valid product: " << pd << std::endl; | |
| for (int i = idx; i >= 0; i -- ) { | |
| int new_xor = xr ^ primes[i]; | |
| if (remain < primes[i]) continue; | |
| res += dfs_953_old(primes, i, new_xor, pd * primes[i], N); | |
| } | |
| return res; | |
| } | |
| #define MO 1000000007 | |
| __int128 dfs_953(const std::vector<int> &primes, int idx, long long xr, __int128 pd, __int128 N) { | |
| // std::cout << "dfs called with idx: " << idx << ", xr: " << xr << ", pd: " << pd << std::endl; | |
| if (pd > N) return 0; | |
| __int128 remain = N / pd + 1; | |
| if (xr > primes[idx] * 2) return 0; | |
| __int128 res = 0; | |
| if (xr == 0) { | |
| __int128 cnt = 0, sum = 0; | |
| __int128 max_valid = (sqrt(N / pd + 1e-8)) + 1; | |
| while (max_valid * max_valid * pd > N) { | |
| max_valid--; | |
| } | |
| cnt = max_valid; | |
| sum = (max_valid * (max_valid + 1) * (2 * max_valid + 1) / 6 % MO * pd) % MO; | |
| res = sum; | |
| // std::cout << "Found valid product: " << pd << ", count: " << cnt | |
| // << ", sum: " << sum << std::endl; | |
| } | |
| int prime_pos = std::lower_bound(primes.begin(), primes.end(), remain) - primes.begin() + 2; | |
| prime_pos = std::min(prime_pos, idx - 1); | |
| for (int i = prime_pos; i >= 0; i -- ) { | |
| int new_xor = xr ^ primes[i]; | |
| if (remain < primes[i]) continue; | |
| res += dfs_953(primes, i, new_xor, pd * primes[i], N); | |
| } | |
| return res % MO; | |
| } | |
| void P953() { | |
| __int128 N = 100000000000000LL; // 1e14 | |
| // __int128 N = 10000000LL; | |
| std::vector<int> primes; | |
| auto pc = primecount(sqrt((long long)N) + 1, primes); | |
| std::cout << pc << " primes found up to " << sqrt((long long)N) + 1 << std::endl; | |
| __int128 res = 0, res_old = 0; | |
| std::vector<__int128> res_vec(primes.size(), 0); | |
| #pragma omp parallel for schedule(static, 1) | |
| // for (int i = primes.size() - 1; i < primes.size(); i++) { | |
| for (int i = 0; i < primes.size(); i++) { | |
| // res += dfs_953(primes, i, primes[i], primes[i], N); | |
| res_vec[i] = dfs_953(primes, i, primes[i], primes[i], N); | |
| if (i % 1000 == 0) { | |
| std::cout << "Processed " << i << " primes (" << primes[i] << ")" << std::endl; | |
| } | |
| } | |
| for (auto i : res_vec) { | |
| res += i; | |
| } | |
| for (__int128 i = 1; i * i <= N; i ++ ) | |
| res = (res + i * i) % MO; | |
| // for (int i = 0; i < primes.size(); i++) { | |
| // res_old += dfs_953_old(primes, i, primes[i], primes[i], N); | |
| // } | |
| // std::cout << res << ' ' << res_old << std::endl; | |
| std::cout << "Result: " << (long long)res << std::endl; | |
| } | |
| int main() { | |
| // P954() | |
| // P001(); | |
| P953(); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment