fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <numeric>
  5.  
  6. using namespace std;
  7.  
  8. int n;
  9. string A, B;
  10. long long max_nwd = 1;
  11.  
  12. // Szybka funkcja obliczająca NWD za pomocą algorytmu Euklidesa
  13. long long gcd(long long a, long long b) {
  14.     while (b) {
  15.         a %= b;
  16.         swap(a, b);
  17.     }
  18.     return a;
  19. }
  20.  
  21. void dfs(int idx, long long cur_x, long long cur_y, long long max_possible_x, long long max_possible_y) {
  22.     // Jeśli maksymalny możliwy wynik w tej gałęzi nie ma szans przebić obecnego max_nwd, odcinamy poddrzewo
  23.     // Górne ograniczenie dla NWD(x, y) to min(x, y)
  24.     if (min(max_possible_x, max_possible_y) <= max_nwd) {
  25.         return;
  26.     }
  27.  
  28.     if (idx == n) {
  29.         if (cur_x > 0 && cur_y > 0) {
  30.             long long current_nwd = gcd(cur_x, cur_y);
  31.             if (current_nwd > max_nwd) {
  32.                 max_nwd = current_nwd;
  33.             }
  34.         }
  35.         return;
  36.     }
  37.  
  38.     int start_a = (A[idx] == '?') ? 0 : (A[idx] - '0');
  39.     int end_a = (A[idx] == '?') ? 9 : (A[idx] - '0');
  40.  
  41.     int start_b = (B[idx] == '?') ? 0 : (B[idx] - '0');
  42.     int end_b = (B[idx] == '?') ? 9 : (B[idx] - '0');
  43.  
  44.     for (int da = start_a; da <= end_a; ++da) {
  45.         long long next_x = cur_x * 10 + da;
  46.         long long next_max_x = max_possible_x * 10 + da;
  47.  
  48.         for (int db = start_b; db <= end_b; ++db) {
  49.             long long next_y = cur_y * 10 + db;
  50.             long long next_max_y = max_possible_y * 10 + db;
  51.  
  52.             dfs(idx + 1, next_x, next_y, next_max_x, next_max_y);
  53.         }
  54.     }
  55. }
  56.  
  57. int main() {
  58.     ios_base::sync_with_stdio(false);
  59.     cin.tie(NULL);
  60.  
  61.     if (!(cin >> n >> A >> B)) return 0;
  62.  
  63.     // Obliczamy maksymalne możliwe wartości (gdzie '?' zamieniamy na '9')
  64.     long long initial_max_x = 0, initial_max_y = 0;
  65.     for (int i = 0; i < n; ++i) {
  66.         int da = (A[i] == '?') ? 9 : (A[i] - '0');
  67.         int db = (B[i] == '?') ? 9 : (B[i] - '0');
  68.         initial_max_x = initial_max_x * 10 + da;
  69.         initial_max_y = initial_max_y * 10 + db;
  70.     }
  71.  
  72.     dfs(0, 0, 0, initial_max_x, initial_max_y);
  73.  
  74.     cout << max_nwd << "\n";
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 2.2s 5316KB
comments (?)
stdin
copy 
9
246666664
??????0?9
stdout
copy 
1622807
https://ideone.com/O4KCfz
language:
C++14 (gcc 8.3)
created:
10 hours 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!