Codeforces Round #281 (Div. 2)_html/css_WEB-ITnose

This question is not difficult either.

But I keep making mistakes. Either I misread the question or the array is too small.

A, B, C, and D are all pretty easy. E is actually quite simple, but I didn’t understand it at the time. .

If C, just enumerate all possible d, and the complexity is sorted nlogn

D , For odd numbers, Black only needs to move symmetrically with White to win

For even numbers, White takes one step to 1, 2 and it becomes an odd number situation, and then Black moves, White just needs to move symmetrically. So in the end White will definitely win

E

For the given t, a, b

We first judge the special Done,

It’s nothing more than the case of t = 1, a=1

Special judgment based on whether b is equal to 1

And then the rest The situation depends on the equation

a0 a1t a2t^2 ...=a

a0 a1a a2a^2 ...=b

Then move the terms to get

a1 a2t a3t^2 ...= (a-a0)/t

a1 a2a a3a^2 ...= (b-a0) /a

You will find that this problem can be solved recursively.

The value of a0 here has requirements

(a-a0) %t ==0

(b-a0)%a==0

In other words, a0%a == b % a, a0 % t == a % t

Then we found that the amount of enumerating a0 is actually very small

For a0%a == b %a has a0= k * a b �

a0 will find k=0 or 1, and it must satisfy a0 % t == a % t

Then the next step is recursion. Here’s the answer

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <cmath>#include <algorithm>#include <map>#define MAXN 55555#define MAXM 222222#define INF 1000000001using namespace std;int gao(long long a, long long b, long long c, long long d) {    if(b == 0 && d == 0) return 1;    if(b == 0 || d == 0) return 0;    long long ans = 0;    for(long long i = 0; i  b || a0 > d) break;        if((b - a0) % a == 0) {            ans += gao(a, (b - a0) / a, c, (d - a0) / c);        }    }    return ans;}int main() {    long long t, a, b;    scanf("%I64d%I64d%I64d", &t, &a, &b);    if(t == 1 && a == 1) {        if(b == 1) {            puts("inf");        } else puts("0");    } else printf("%d\n", gao(t, a, a, b));    return 0;}</map></algorithm></cmath></queue></cstring></cstdio></iostream>