codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1562.md (22106B)


      1 Source: https://codeforces.com/blog/entry/94278
      2 
      3 Will we, will you...  
      4 Can we, can you, can we change?
      5 
      6 [1562A - The Miracle and the Sleeper](/contest/1562/problem/A "Codeforces Round 741 (Div. 2)")
      7 
      8 **Hint 1**
      9 
     10 Try to consider such segments where $l \le \lfloor \frac{r}{2} \rfloor + 1$.
     11 
     12 **Hint 2**
     13 
     14 Now think about what to do if this condition is not satisfied.
     15 
     16 **Solution**
     17 
     18 Tutorial is loading...
     19 
     20 **Code C++ (Wind_Eagle)**
     21 
     22 ```
     23 #include <iostream>
     24 
     25 using namespace std;
     26 
     27 int l, r;
     28 
     29 void solve() {
     30     if (r < l * 2) {
     31         cout << r - l << endl;
     32     }
     33     else {
     34         cout << (r - 1) / 2 << endl;
     35     }
     36 }
     37 
     38 int main() {
     39     int t;
     40     cin >> t;
     41     while (t--) {
     42         cin >> l >> r;
     43         solve();
     44     }
     45 }
     46 ```
     47 
     48 [1562B - Scenes From a Memory](/contest/1562/problem/B "Codeforces Round 741 (Div. 2)")
     49 
     50 **Hint 1**
     51 
     52 Try to consider small numbers, such as those consisting of three digits.
     53 
     54 **Hint 2**
     55 
     56 Now think about what the maximum number of digits can be in the optimal answer.
     57 
     58 **Solution**
     59 
     60 Tutorial is loading...
     61 
     62 **Code C++ (Wind_Eagle)**
     63 
     64 ```
     65 #include <iostream>
     66 
     67 using namespace std;
     68 
     69 int n;
     70 
     71 string s;
     72 
     73 bool prime[100];
     74 
     75 void solve() {
     76     for (int i = 0; i < n; i++) {
     77         if (s[i] == '1' || s[i] == '4' || s[i] == '6' || s[i] == '8' || s[i] == '9') {
     78             cout << 1 << endl;
     79             cout << s[i] << endl;
     80             return;
     81         }
     82     }
     83     for (int i = 0; i < n; i++) {
     84         for (int j = i + 1; j < n; j++) {
     85             if (!prime[(s[i] - '0') * 10 + (s[j] - '0')]) {
     86                 cout << 2 << endl;
     87                 cout << s[i] << s[j] << endl;
     88                 return;
     89             }
     90         }
     91     }
     92     exit(42);
     93 }
     94 
     95 int main() {
     96     for (int i = 2; i < 100; i++) {
     97         prime[i] = true;
     98         for (int j = 2; j * j <= i; j++) {
     99             if (i % j == 0) {
    100                 prime[i] = false;
    101             }
    102         }
    103     }
    104     int t;
    105     cin >> t;
    106     while (t--) {
    107         cin >> n;
    108         cin >> s;
    109         solve();
    110     }
    111 }
    112 ```
    113 
    114 **Additional Problem 1**
    115 
    116 Try to prove that the author's solution works for $O(k)$ for one test case.
    117 
    118 **Solution of Additional Problem 1**
    119 
    120 Finding an answer consisting of one digit works in $O(k)$. Now let's see how long the loop takes to complete. Indeed, it is easy to see that once the pairs of indexes $(0,1)$, $(0,2)$, and $(1,2)$ are considered, an answer will always be found. This is so because in any number of three digits you can find an answer consisting of two digits (this was proved earlier). So this is equivalent to removing all but the first three digits, and then solving the problem for them (assuming that the length of the optimal answer is two).
    121 
    122 **Additional Problem 2**
    123 
    124 Try to think of a way to search index pairs and a test such that this search works for $O(k^2)$ per test case.
    125 
    126 **Solution of Additional Problem 2**
    127 
    128 Let's take the string \t{3737 \ldots 37} as a string. We will search pairs of indices in the following way: first we will search all pairs of indices with different parities, and then all pairs of indices with the same parity. It is easy to see that such a search will work for $O(k^2)$ for one test case, because all pairs of indices with different parity will give numbers $37$ and $73$, which are prime, and there are $O(k^2)$ such pairs.
    129 
    130 [1562C - Rings](/contest/1562/problem/C "Codeforces Round 741 (Div. 2)")
    131 
    132 **Hint 1**
    133 
    134 Think about whether a suitable $k$ (such that $f(t) = f(w) \cdot k$) can be made small? What small $k$ is easy to multiply binary numbers by?
    135 
    136 **Hint 2**
    137 
    138 Such $k$ can be the numbers $0$, $1$, and $2$~--- multiplying by $0$ gives $0$, multiplying by $1$ leaves the number as is, and multiplying by $2$ adds a zero to the end. Think about how you can take advantage of this.
    139 
    140 **Solution**
    141 
    142 Tutorial is loading...
    143 
    144 **Code C++ (Wind_Eagle)**
    145 
    146 ```
    147 #include <iostream>
    148 
    149 using namespace std;
    150 
    151 int main() {
    152     int t;
    153     cin >> t;
    154     while (t--) {
    155         int n;
    156         cin >> n;
    157         string s;
    158         cin >> s;
    159         bool solved = false;
    160         for (int i = 0; i < n; i++) {
    161             if (s[i] == '0') {
    162                 solved = true;
    163                 if (i >= n / 2) {
    164                     cout << 1 << " " << i + 1 << " " << 1 << " " << i << endl;
    165                     break;
    166                 } else {
    167                     cout << i + 2 << " " << n << " " << i + 1 << " " << n << endl;
    168                     break;
    169                 }
    170             }
    171         }
    172         if (!solved) {
    173             cout << 1 << " " << n - 1 << " " << 2 << " " << n << endl;
    174         }
    175     }
    176 }
    177 ```
    178 
    179 **Additional Problem 1**
    180 
    181 Think about how the problem would be solved if any other number system was chosen, given all the previous conditions (the string consists of the digits $0$ and $1$, the string contains at least one one).
    182 
    183 **Solution of Additional Problem 1**
    184 
    185 The solution would not change in any way. In fact, in a number system with base $k$, adding a zero to the left side does not change the number (multiplication by $1$), but adding a zero to the right side increases the number $k$ times (multiplication by $k$).
    186 
    187 **Additional Problem 2**
    188 
    189 Think about how the problem would be solved if the condition sounded like this: \textit{it is necessary that $f(t)$ is divisible by $f(w)$. There are at least one one in the array. Zero is divisible by all numbers, but no number is divisible by zero. Zero is not divisible by zero.}
    190 
    191 **Solution of Additional Problem 2**
    192 
    193 In fact, the problem gets a little more complicated. For example, consider this test: \t{111000000}. In this case, we could not output $4$ $9$ $5$ $9$ because zero is not divisible by zero.
    194 
    195 We will perform the old solution, but check that we are not trying to divide zero by zero (if we divide something by zero, we will swap the numbers). And if the answer is not found, then either the whole left half of the string consists of zeros, or the whole right half. Let the leftmost unit have position $p1$, and the rightmost unit ~--- position $p2$. Then in the first case you can output $1$ $p2$ $2$ $p2$, and in the second case~--- $p1$ $n$ $p1$ $n-1$.
    196 
    197 It is not hard to see that such a solution will always find the answer.
    198 
    199 In fact, we can solve the problem even simpler: when we meet zero in the left half, we additionally check whether there is at least one one among the characters on the right. If there is, we print the answer, otherwise we move on. Similarly, when we encounter zero in the right half, we additionally check if there is at least one one among the characters on the left. We can show that this solution will also always find the answer.
    200 
    201 It is interesting that we have solved \textbf{a stronger version of the problem}, since the solution we obtained works correctly for the old problem as well.
    202 
    203 [1562D1 - Two Hundred Twenty One (easy version)](/contest/1562/problem/D1 "Codeforces Round 741 (Div. 2)")
    204 
    205 **Hint 1**
    206 
    207 Think about: how is the parity of the length of the segment and the parity of the number of elements to be removed related?
    208 
    209 **Hint 2**
    210 
    211 Think about how much and how the value of the sign-variable sum differs when only one element is removed, and when only its neighbor is removed.
    212 
    213 **Hint 3**
    214 
    215 Consider odd-length segments. Try to take small segments and for each element find out what the sign-variable sum will be after it is removed. After that you may notice something interesting.
    216 
    217 **Solution**
    218 
    219 Tutorial is loading...
    220 
    221 **Code C++ (Wind_Eagle)**
    222 
    223 ```
    224 #include <iostream>
    225 
    226 using namespace std;
    227 
    228 int a[1000000 + 5], p[1000000 + 5];
    229 
    230 int get_sum(int l, int r) {
    231     if (l > r) {
    232         return 0;
    233     }
    234     return (l % 2 == 1) ? p[r] - p[l - 1] : p[l - 1] - p[r];
    235 }
    236 
    237 int main() {
    238     ios_base::sync_with_stdio(false);
    239     cin.tie(nullptr);
    240     int t;
    241     cin>>t;
    242     while (t--) {
    243         int n, q;
    244         cin >> n >> q;
    245         string ss;
    246         cin >> ss;
    247         for (int i = 1; i <= n; i++) {
    248             a[i] = (ss[i - 1] == '+' ? 1 : -1);
    249         }
    250         p[0] = 0;
    251         for (int i = 1; i <= n; i++) {
    252             p[i] = p[i - 1] + (i % 2 == 1 ? a[i] : -a[i]);
    253         }
    254         for (int o = 0; o < q; o++) {
    255             int l, r;
    256             cin >> l >> r;
    257             if (get_sum(l, r) == 0) {
    258                 cout << "0\n";
    259                 continue;
    260             }
    261             if ((r - l + 1) % 2 == 0) {
    262                 cout << "2\n";
    263             }
    264             else {
    265                 cout << "1\n";
    266             }
    267         }
    268     }
    269 }
    270 ```
    271 
    272 [1562D2 - Two Hundred Twenty One (hard version)](/contest/1562/problem/D2 "Codeforces Round 741 (Div. 2)")
    273 
    274 **Hints 1-3**
    275 
    276 See the corresponding hints from Problem D1.
    277 
    278 **Hint 4**
    279 
    280 Consider how to quickly check the value of a sign-variable sum on a segment if you know that exactly one element is removed from it (and know the number of that element).
    281 
    282 **Hint 5**
    283 
    284 From the solution of Problem D1 it is clear that for any odd segment only one element has to be removed. Consider how to find such an element, based on the proof of its existence given above.
    285 
    286 **Solution**
    287 
    288 Tutorial is loading...
    289 
    290 **Code C++ (Wind_Eagle)**
    291 
    292 ```
    293 #include <iostream>
    294 
    295 using namespace std;
    296 
    297 int a[1000000 + 5], p[1000000 + 5];
    298 
    299 int get_sum(int l, int r) {
    300     if (l > r) {
    301         return 0;
    302     }
    303     return (l % 2 == 1) ? p[r] - p[l - 1] : p[l - 1] - p[r];
    304 }
    305 
    306 int check_elimination(int l, int r, int m) {
    307     return ((m - l + 1) % 2 == 1)
    308     ? get_sum(l, m - 1) + get_sum(m + 1, r)
    309     : get_sum(l, m - 1) - get_sum(m + 1, r);
    310 }
    311 
    312 int get_sign(int m) {
    313     return m > 0 ? 1 : -1;
    314 }
    315 
    316 int calculate_odd_segment(int l, int r) {
    317     if (l == r) {
    318         return l;
    319     }
    320     int pos = 0;
    321     int lb = l;
    322     int rb = r;
    323     while (lb < rb) {
    324         int mb = (lb + rb) / 2;
    325         int lq = check_elimination(l,r,lb);
    326         int mq = check_elimination(l,r,mb);
    327         int rq = check_elimination(l,r,rb);
    328         if (lq == 0) {
    329             pos = lb;
    330             break;
    331         }
    332         if (mq == 0) {
    333             pos = mb;
    334             break;
    335         }
    336         if (rq == 0) {
    337             pos = rb;
    338             break;
    339         }
    340         if (get_sign(lq) == get_sign(mq)) {
    341             lb = mb;
    342         } else {
    343             rb = mb;
    344         }
    345     }
    346     return pos;
    347 }
    348 
    349 int main() {
    350     ios_base::sync_with_stdio(false);
    351     cin.tie(nullptr);
    352     int t;
    353     cin>>t;
    354     while (t--) {
    355         int n, q;
    356         cin >> n >> q;
    357         string ss;
    358         cin >> ss;
    359         for (int i = 1; i <= n; i++) {
    360             a[i] = (ss[i - 1] == '+' ? 1 : -1);
    361         }
    362         p[0] = 0;
    363         for (int i = 1; i <= n; i++) {
    364             p[i] = p[i - 1] + (i % 2 == 1 ? a[i] : -a[i]);
    365         }
    366         for (int o = 0; o < q; o++) {
    367             int l, r;
    368             cin >> l >> r;
    369             if (get_sum(l, r) == 0) {
    370                 cout << "0\n";
    371                 continue;
    372             }
    373             bool even = false;
    374             if ((r - l + 1) % 2 == 0) {
    375                 even = true;
    376                 l++;
    377             }
    378             int pos = calculate_odd_segment(l, r);
    379             if (even) {
    380                 cout << "2\n" << l - 1 << " "<< pos << '\n';
    381             } else {
    382                 cout << "1\n" << pos << '\n';
    383             }
    384         }
    385     }
    386 }
    387 ```
    388 
    389 **Interesting question**
    390 
    391 Is there a solution with asymptotics $O(n + q)$ for a single test case?
    392 
    393 [1562E - Rescue Niwen!](/contest/1562/problem/E "Codeforces Round 741 (Div. 2)")
    394 
    395 **Hint 1**
    396 
    397 To solve it, you will need to quickly (in O(1)) find the largest common prefix of two substring.
    398 
    399 **Hint 2**
    400 
    401 Take some small strings and try to build the largest increasing subsequence. Maybe there's something special about it.
    402 
    403 **Hint 3**
    404 
    405 Use dynamic programming.
    406 
    407 **Solution**
    408 
    409 Tutorial is loading...
    410 
    411 **Code C++ (Wind_Eagle)**
    412 
    413 ```
    414 #include <iostream>
    415 
    416 using namespace std;
    417 
    418 int16_t lcp[10000 + 5][10000 + 5];
    419 
    420 int dp[10000 + 5];
    421 
    422 bool is_greater(const string& s, int x, int y) {
    423     if (lcp[x][y] == static_cast<int>(s.size()) - x) {
    424         return false;
    425     }
    426     return s[x + lcp[x][y]] > s[y + lcp[x][y]];
    427 }
    428 
    429 int get_score(const string& s, int x, int y) {
    430     if (is_greater(s, x, y)) {
    431         return dp[y] + static_cast<int>(s.size()) - x - lcp[x][y];
    432     }
    433     return 0;
    434 }
    435 
    436 int main() {
    437     int t;
    438     cin >> t;
    439     while (t--) {
    440         int n;
    441         cin >> n;
    442         string s;
    443         cin >> s;
    444         if (s.size() != n) return 42;
    445         for (int i = 0; i <= n; i++) {
    446             for (int j = 0; j <= n; j++) {
    447                 lcp[i][j] = 0;
    448             }
    449         }
    450         for (int i = n - 1; i >= 0; i--) {
    451             for (int j = n - 1; j >= 0; j--) {
    452                 if (i == j) {
    453                     lcp[i][j] = n - i;
    454                 } else
    455                 if (s[i] != s[j]) {
    456                     lcp[i][j] = 0;
    457                 } else {
    458                     lcp[i][j] = lcp[i + 1][j + 1] + 1;
    459                 }
    460             }
    461         }
    462         int ans = n;
    463         dp[0] = n;
    464         for (int i = 1; i < n; i++) {
    465             dp[i] = n - i;
    466             for (int j = 0; j < i; j++) {
    467                 dp[i] = max (dp[i], get_score(s, i, j));
    468             }
    469             ans = max(ans, dp[i]);
    470         }
    471         cout << ans << '\n';
    472     }
    473 }
    474 ```
    475 
    476 **Interesting question**
    477 
    478 As far as I know, using trie, you can sort all substrings of a given string in $O(n^2)$. Also, as far as I know, in C++ programming language *std::lower_bound* works so fast that in an array of size $1.25 \cdot 10^7$ the same number of *std::lower_bound* operations is done in a little less than a second. It is also known that *std::lower_bound* can be used to write a search for the largest increasing subsequence in an array. The question is: can we use this to write a $O(n^2 \cdot log(n))$ solution that passes the tests?
    479 
    480 [1562F - Tubular Bells](/contest/1562/problem/F "Codeforces Round 741 (Div. 2)")
    481 
    482 **Hint 1**
    483 
    484 Come up with a solution that uses $\frac{n \cdot (n-1)}{2}$ queries.
    485 
    486 **Hint 2**
    487 
    488 At $n \lt 100$, apply a solution that uses $\frac{n \cdot (n-1)}{2}$ queries. Now suppose $n \geq 100$. Come up with a solution that would use $\lceil\frac{3n}{2}rceil$ queries.
    489 
    490 **Hint 3**
    491 
    492 When $n \lt 10000$, apply a solution that uses $2n$ queries. Now suppose $n \geq 5000$. Most likely, in the $2n$ queries solution you come up with, you need to find the largest prime number on the segment. Think about it, do you really need **the largest** prime number? Maybe just **enough large** prime number would be enough? How can you find such a number?
    493 
    494 **Hint 4**
    495 
    496 Use probabilistic algorithms to find such a number. Use probabilistic algorithms to also make sure that you have found the right number.
    497 
    498 **Hint 5**
    499 
    500 Now use the prime number you have found to find the largest prime number. You will probably already know most of the numbers when you find it, and you can use the largest prime number to find the rest.
    501 
    502 **Solution**
    503 
    504 Tutorial is loading...
    505 
    506 **Code C++ (Wind_Eagle)**
    507 
    508 ```
    509 #include <iostream>
    510 #include <vector>
    511 #include <algorithm>
    512 #include <cmath>
    513 #include <ctime>
    514 #include <random>
    515 
    516 using namespace std;
    517 
    518 #define int long long
    519 
    520 mt19937 rnd(time(NULL));
    521 
    522 int swnmb[1000000+5];
    523 
    524 int swnmbr[1000000+5];
    525 
    526 int b[1000000+5];
    527 
    528 bool p[1000000+5];
    529 
    530 vector<int> primes;
    531 
    532 int get_lcm(int x, int y)
    533 {
    534     cout<<"? "<<swnmb[x]<<" "<<swnmb[y]<<endl;
    535     int u;
    536     cin>>u;
    537     return u;
    538 }
    539 
    540 int max_fact(int d)
    541 {
    542     for (int j=(int)primes.size()-1; j>=0; j--)
    543     {
    544         if (d%primes[j]==0) return primes[j];
    545     }
    546 }
    547 
    548 vector<int> fact(int d)
    549 {
    550     vector<int> ans;
    551     for (auto j:primes)
    552     {
    553         if (d==1) break;
    554         while (d%j==0)
    555         {
    556             ans.push_back(j);
    557             d/=j;
    558         }
    559     }
    560     return ans;
    561 }
    562 
    563 bool is_prime(int d)
    564 {
    565     for (int j=0; j<(int)primes.size(); j++)
    566     {
    567         if (primes[j]>500) return true;
    568         if (d%primes[j]==0) return false;
    569     }
    570     return true;
    571 }
    572 
    573 int paired_get_lcm[100+5][100+5];
    574 
    575 void solve_quadric(int n)
    576 {
    577     for (int i=1; i<=n; i++) {
    578         for (int j=i+1; j<=n; j++) {
    579             paired_get_lcm[i][j]=get_lcm(i,j);
    580             paired_get_lcm[j][i]=paired_get_lcm[i][j];
    581         }
    582     }
    583     int m1=0;
    584     int m2=0;
    585     int mx=0;
    586     for (int i=1; i<=n; i++) {
    587         for (int j=i+1; j<=n; j++) {
    588             if (paired_get_lcm[i][j]>mx)
    589             {
    590                 mx=paired_get_lcm[i][j];
    591                 m1=i;
    592                 m2=j;
    593             }
    594         }
    595     }
    596     int u=0;
    597     for (int i=1; i<=200000; i++)
    598     {
    599         if (mx==i*(i+1))
    600         {
    601             u=i+1;
    602             break;
    603         }
    604     }
    605     for (int i=1; i<=n; i++)
    606     {
    607         if (i==m1||i==m2) continue;
    608         if (paired_get_lcm[m1][i]%u!=0)
    609         {
    610             swap(m1,m2);
    611             break;
    612         }
    613     }
    614     b[m1]=u;
    615     int pos=m2;
    616     for (int v=u-1; v>u-n-1; v--)
    617     {
    618         int m0=0;
    619         int mx=0;
    620         for (int j=1; j<=n; j++) {
    621             if (b[j]!=0) continue;
    622             if (pos==j) continue;
    623             if (paired_get_lcm[pos][j]>mx)
    624             {
    625                 mx=paired_get_lcm[pos][j];
    626                 m0=j;
    627             }
    628         }
    629         b[pos]=v;
    630         pos=m0;
    631     }
    632     b[pos]=u-n+1;
    633 }
    634 
    635 void solve_pair(int n)
    636 {
    637     int maxnum=0;
    638     int maxpos=0;
    639     int notmaxpos=0;
    640     for (int i=1; i<=n; i+=2)
    641     {
    642         int u;
    643         if (i!=n) u=get_lcm(i,i+1);
    644         else u=get_lcm(i-1,i);
    645         int w=max_fact(u);
    646         if (w>maxnum)
    647         {
    648             maxnum=w;
    649             maxpos=min(i+1,n);
    650         } else {
    651             notmaxpos=i;
    652         }
    653     }
    654     int cur=get_lcm(notmaxpos,maxpos);
    655     if (cur%maxnum!=0) {
    656         maxpos--;
    657     }
    658     b[maxpos]=maxnum;
    659     for (int i=1; i<=n; i++)
    660     {
    661         if (i==maxpos) continue;
    662         int u=get_lcm(i,maxpos)/maxnum;
    663         b[i]=u;
    664     }
    665 }
    666 
    667 void print_ans(int n)
    668 {
    669     cout<<"! ";
    670     for (int i=1; i<=n; i++) {
    671         cout<<b[swnmbr[i]];
    672         if (i!=n) cout<<" ";
    673     }
    674     cout<<endl;
    675 }
    676 
    677 int32_t main()
    678 {
    679     for (int i=2; i<=200000; i++)
    680     {
    681         if (p[i]) continue;
    682         for (int j=i*i; j<=200000; j+=i)
    683         {
    684             p[j]=true;
    685         }
    686         primes.push_back(i);
    687     }
    688     int t;
    689     cin>>t;
    690     while (t--)
    691     {
    692         int n;
    693         cin>>n;
    694         for (int i=1; i<=n; i++) {
    695             swnmb[i]=0;
    696             swnmbr[i]=0;
    697             b[i]=0;
    698         }
    699         for (int i=1; i<=n; i++) {
    700             swnmb[i]=i;
    701         }
    702         for (int i=1; i<=n*5; i++) {
    703             swap(swnmb[rnd()%n+1], swnmb[rnd()%n+1]);
    704         }
    705         for (int i=1; i<=n; i++) {
    706             swnmbr[swnmb[i]]=i;
    707         }
    708         if (n<100) {
    709             solve_quadric(n);
    710             print_ans(n);
    711             continue;
    712         }
    713         if (n<10000) {
    714             solve_pair(n);
    715             print_ans(n);
    716             continue;
    717         }
    718         int t1=0;
    719         int t2=0;
    720         int pos1=0;
    721         int pos2=0;
    722         for (int i=1; i<=4000; i++)
    723         {
    724             int i1=rnd()%n+1;
    725             int i2=rnd()%n+1;
    726             while (i1 == i2) {
    727                 i2=rnd()%n+1;
    728             }
    729             vector<int> f=fact(get_lcm(i1,i2));
    730             if (f.size()==2&&f[0]>500&&f[1]>500)
    731             {
    732                 bool first1=true;
    733                 bool first2=true;
    734                 for (int j=0; j<100; j++)
    735                 {
    736                     int t=rnd()%n+1;
    737                     while (t==i1||t==i2)
    738                     {
    739                         t=rnd()%n+1;
    740                     }
    741                     if (get_lcm(i1,t)%f[0]!=0)
    742                     {
    743                         first1=false;
    744                         break;
    745                     }
    746                 }
    747                 for (int j=0; j<100; j++)
    748                 {
    749                     int t=rnd()%n+1;
    750                     while (t==i1||t==i2)
    751                     {
    752                         t=rnd()%n+1;
    753                     }
    754                     if (get_lcm(i1,t)%f[1]!=0)
    755                     {
    756                         first2=false;
    757                         break;
    758                     }
    759                 }
    760                 if (first1&&first2)
    761                 {
    762                     bool second1=true;
    763                     for (int j=0; j<100; j++)
    764                     {
    765                         int t=rnd()%n+1;
    766                         while (t==i1||t==i2)
    767                         {
    768                             t=rnd()%n+1;
    769                         }
    770                         if (get_lcm(i2,t)%f[1]!=0)
    771                         {
    772                             second1=false;
    773                             break;
    774                         }
    775                     }
    776                     if (second1)
    777                     {
    778                         t2=f[0]*f[1];
    779                         t1=f[0];
    780                     }
    781                     else
    782                     {
    783                         t2=f[0]*f[1];
    784                         t1=f[1];
    785                     }
    786                     pos1=i2;
    787                     pos2=i1;
    788                 }
    789                 else
    790                 {
    791                     if (!first1)
    792                     {
    793                         t1=f[1];
    794                         t2=f[0];
    795                     }
    796                     else
    797                     {
    798                         t1=f[0];
    799                         t2=f[1];
    800                     }
    801                     pos1=i1;
    802                     pos2=i2;
    803                 }
    804                 b[pos1]=t1;
    805                 b[pos2]=t2;
    806                 int posf=0;
    807                 int maxf=0;
    808                 for (int j=1; j<=n; j++)
    809                 {
    810                     if (j==i1||j==i2) continue;
    811                     int u=get_lcm(pos1,j);
    812                     if (u/t1>500)
    813                     {
    814                         b[j]=u/t1;
    815                         if (is_prime(b[j]))
    816                         {
    817                             if (b[j]>maxf)
    818                             {
    819                                 maxf=b[j];
    820                                 posf=j;
    821                             }
    822                         }
    823                     }
    824                 }
    825                 for (int j=1; j<=n; j++)
    826                 {
    827                     if (b[j]!=0) continue;
    828                     b[j]=get_lcm(posf,j)/b[posf];
    829                 }
    830                 break;
    831             }
    832         }
    833         print_ans(n);
    834     }
    835 }
    836 ```