АГАРТА ІСНУЄ#12268

АГАРТА ІСНУЄ (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редаговано:	Hasan Saleh (MathModel)

Рішення

(Ми будемо посилатися на поточне значення $n$ після всіх операцій як $cur$ )

$cur$ не може стати негативним у будь-який момент, тому що тоді як M-операції, так і S-операції зроблять його ще більш негативним, тому він ніколи не досягне $0$ . Це означає, що для того, щоб зробити $cur$ рівним $0$ , спочатку ми повинні зробити його кратним $z$ $(cur mod z = 0)$ (\text{cur}\mod z = 0), а потім продовжувати виконувати S-операції, поки не отримаємо $0$ .

Спочатку розглянемо випадки $- 1$ . Як ми вже сказали, $cur$ не може бути негативним, тому якщо $n$ спочатку негативне, то відповідь $- 1$ .

Інший випадок $- 1$ - це якщо ми не можемо зробити $cur$ кратним $z$ . Досить перевірити значення $(n \cdot x^{z} \cdot y^{z}) mod z$ (n \cdot x^z \cdot y^z)\mod z, якщо воно не $0$ , то ми не можемо зробити $n$ кратним $z$ .

Доказ: Оскільки існує лише $z$ різних значень $c u r mod z$ cur\mod z, множення більше ніж $z$ разів призведе нас до циклу.

Тепер, коли ми закінчили з випадками $- 1$ , ми завжди матимемо відповідь.

Ми чітко бачимо, що в оптимальному рішенні ми ніколи не будемо виконувати M-операцію, якщо $cur < z$ \text{cur} < z є істинним, тому що якщо $cur \geq z$ \text{cur} \ge z, ми можемо продовжувати виконувати S-операції, поки $cur < z$ \text{cur} < z, це тому, що $cur mod z = (cur - z) mod z$ \text{cur}\mod z = (\text{cur}-z)\mod z, і оскільки невиконання S-операцій перед M-операцією вимагатиме від нас виконати більше S-операцій у майбутньому, що явно не є оптимальним.

Розглянемо випадок, коли $x = y$ x=y:

Твердження: Ми не будемо виконувати більше ніж $lo g (z)$ M-операцій.

Доказ: Щоб $cur$ було кратним $z$ , $cur$ повинно мати всі прості множники $z$ . Коли ми виконуємо M-операцію, ми додаємо прості множники до $cur$ , і максимальна різниця між кількістю появ простого множника в $z$ і кількістю появ того ж простого множника в $cur$ становить $lo g (z)$ , тому нам не потрібно більше ніж $lo g (z)$ M-операцій, щоб зробити $cur$ мати всі прості множники $z$ .

Це означає, що для $x = y$ x=y ми можемо просто продовжувати виконувати M-операції, поки $cur < z$ \text{cur} < z, і якщо $cur$ коли-небудь стане більшим за $z$ , ми можемо зробити $cur$ рівним $cur mod z$ \text{cur}\mod z з вартістю $⌊ \frac{cur}{z} ⌋$ \left \lfloor{\frac{\text{cur}}{z}} \right \rfloor (повторно виконуючи S-операції), ми зупиняємося, коли $cur = 0$ \text{cur}=0.

Тепер, щоб вирішити повну задачу, давайте спочатку визначимо стан ( $i, j$ ) як стан, де ми помножили $i$ разів на $x$ і $j$ разів на $y$ , і $cur$ повинно дорівнювати $(n \cdot x^{i} \cdot y^{j}) mod z$ (n \cdot x^i \cdot y^j)\mod z (ми будемо посилатися на значення $cur$ у цьому стані як $cur [i] [j]$ \text{cur}[i][j]).

Ми можемо використовувати підхід динамічного програмування:

$dp [i] [j]$ \text{dp}[i][j] дорівнює мінімальній можливій вартості для досягнення стану ( $i, j$ )

Базовий випадок:

dp [0] [0] = ⌊ \frac{n}{z} ⌋

\text{dp}[0][0] = \left \lfloor{\frac{n}{z}} \right \rfloor

Перехід:

dp [i] [j] = min (dp [i - 1] [j] + ⌊ \frac{cur [ i - 1 ] [ j ] \cdot x}{z} ⌋, dp [i] [j - 1] + ⌊ \frac{cur [ i ] [ j - 1 ] \cdot y}{z} ⌋)

\text{dp}[i][j] = \min(\text{dp}[i-1][j] + \left \lfloor{\frac{\text{cur}[i-1][j] \cdot x}{z}} \right \rfloor , \text{dp}[i][j-1] + \left \lfloor{\frac{\text{cur}[i][j-1] \cdot y}{z}} \right \rfloor)

Відповідь - це мінімальне значення $dp [i] [j]$ \text{dp}[i][j], де $cur [i] [j] = 0$ \text{cur}[i][j] = 0.

Тепер, оскільки ми не будемо виконувати більше ніж $z$ M-операцій, складність для dp становить $O (z^{2})$ \mathcal{O}(z^2), що є занадто великим.

Як ми вже сказали в рішенні для $x = y$ x=y, нам не потрібно більше ніж $lo g (z)$ M-операцій, щоб зробити $cur$ кратним $z$ . Це означає, що ми завжди можемо отримати відповідь менше ніж $1 0^{11}$ 10^{11}. Оскільки максимальна відповідь, яку ми могли б отримати, якщо ми виконали M-операції довільно, становить $lo g (z) \cdot ⌊ \frac{m a x ( x , y ) \cdot ( z - 1 )}{z} ⌋ + lo g (z) \cdot (lo g (z) + 1)$ \log(z) \cdot \left \lfloor{\frac{\max(x,y) \cdot (z-1)}{z}}\right \rfloor + \log(z) \cdot (\log(z)+1), що строго менше ніж $1 0^{11}$ 10^{11}.

Оскільки відповідь завжди менше ніж $1 0^{11}$ 10^{11}, ми не будемо виконувати більше ніж $5 \cdot 1 0^{5}$ 5\cdot10^5 M-операцій, оскільки вартість їх самих була б більшою ніж $1 0^{11}$ 10^{11}.

Це оптимізує рішення dp до $O (1 0^{11})$ \mathcal{O}(10^{11}), зробивши $5 \cdot 1 0^{5}$ 5 \cdot 10^5 межою для $i, j$ , але це все ще занадто повільно.

Давайте спостерігати за станом ( $i, j$ ), де обидва $i$ та $j$ строго більші за $lo g (z)$ , гарантовано, що $cur [i - 1] [j] = cur [i] [j - 1] = 0$ \text{cur}[i-1][j]=\text{cur}[i][j-1]=0, і оскільки $min (dp [i - 1] [j], dp [i] [j - 1]) \leq dp [i] [j]$ \min(\text{dp}[i-1][j],\text{dp}[i][j-1]) \le \text{dp}[i][j], нам не важливо стан ( $i, j$ ), оскільки ми вже маємо кращу відповідь.

Тепер ми можемо виконати попередній dp двічі, перший раз з $i \leq lo g (z), j \leq 5 \cdot 1 0^{5}$ i \le \log(z) , j \le 5 \cdot 10^5, і другий раз з $i \leq 5 \cdot 1 0^{5}, j \leq lo g (z)$ i \le 5 \cdot 10^5 , j \le \log(z).

Отже, загальна складність коду становить $O (5 \cdot 1 0^{5} \cdot lo g (z))$ \mathcal{O}(5 \cdot 10^5 \cdot \log(z)), що достатньо швидко, щоб пройти.


#include<bits/stdc++.h>
#define ll long long
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
 
using namespace std;

const ll N = 500000 , lg = 35;

ll n , x , y , z , ans = LLONG_MAX;
ll dp[lg][N];
ll md[2][N];

ll fp(ll a , ll b)
{
    if(b==0)
        return 1;
    ll c = fp(a,b/2);
    if(b%2)
        return c*c%z*a%z;
    else
        return c*c%z;
}

ll Mcost(ll a)
{
    return a*(a+1)/2;
}

void rec(ll a , ll b)
{
    dp[0][0]=n/z;
    md[0][0]=md[1][0]=1;
    for(int i = 1 ; N>i ; i++)
    {
        md[0][i]=md[0][i-1]*a%z;
        md[1][i]=md[1][i-1]*b%z;
    }
    for(int i = 1 ; lg>i ; i++)
    {
        ll p = n*md[0][i-1]%z;
        p*=a;
        dp[i][0]=dp[i-1][0]+p/z;
    }
    for(int i = 1 ; N>i ; i++)
    {
        ll p = n*md[1][i-1]%z;
        p*=b;
        dp[0][i]=dp[0][i-1]+p/z;
    }
    for(int i = 1 ; lg>i ; i++)
    {
        for(int j = 1 ; N>j ; j++)
        {
            ll p = n*md[0][i-1]%z*md[1][j]%z;
            p*=a;
            dp[i][j]=dp[i-1][j]+p/z;
            p = n*md[0][i]%z*md[1][j-1]%z;
            p*=b;
            dp[i][j]=min(dp[i][j],dp[i][j-1]+p/z);
        }
    }
    for(int i = 0 ; lg>i ; i++)
    {
        for(int j = 0 ; N>j ; j++)
        {
            if(n*md[0][i]%z*md[1][j]%z==0)
                ans=min(ans,dp[i][j]+Mcost(i+j));
        }
    }
}

int main()
{
    d3
    cin >> n >> x >> y >> z;
    ll e = n*fp(x,100)%z*fp(y,100)%z;
    if(n<0||e!=0)
    {
        cout << -1;
        return 0;
    }
    rec(x,y);
    rec(y,x);
    cans
}