AGARTHA GERÇƏKDİR (Həll təhlili)

Həll

(Biz bütün əməliyyatlardan sonra $n$-in cari dəyərinə $\text{cur}$ deyəcəyik)

$\text{cur}$ heç vaxt mənfi ola bilməz, çünki o zaman həm M-əməliyyatları, həm də S-əməliyyatları onu daha da mənfi edəcək, buna görə də $0$-a çatmayacaq. Bu, $\text{cur}$-u $0$-a bərabər etmək üçün əvvəlcə onu $z$-in tam böləni etməliyik (\text{cur}\mod z = 0) və sonra $0$-a çatana qədər S-əməliyyatlarını davam etdirməliyik.

İlk öncə $-1$ halları ilə məşğul olaq. Daha əvvəl dediyimiz kimi, $\text{cur}$ mənfi ola bilməz, buna görə də əgər $n$ ilkin olaraq mənfidirsə, cavab $-1$-dir.

Digər $-1$ halı $\text{cur}$-u $z$-in tam böləni edə bilmədiyimizdir. n \cdot x^z \cdot y^z \mod z dəyərini yoxlamaq kifayətdir, əgər $0$-a bərabər deyilsə, onda $n$-i $z$-in tam böləni edə bilmirik.

Sübut: \text{cur}\mod z dəyərləri yalnız $z$ fərqli olduğuna görə, $z$-dən çox dəfə vurmaq bizi bir dövrə gətirəcək.

İndi $-1$ halları ilə işimiz bitdi, biz həmişə bir cavab alacağıq.

Aydındır ki, optimal həlldə \text{cur} < z olduğu halda M-əməliyyatı etməyəcəyik, çünki əgər \text{cur} \ge z-dirsə, S-əməliyyatlarını davam etdirə bilərik ki, \text{cur} < z olsun, çünki \text{cur}\mod z = (\text{cur}-z)\mod z-dir, və M-əməliyyatından əvvəl S-əməliyyatlarını etməmək gələcəkdə daha çox S-əməliyyatı etməyə məcbur edəcək ki, bu da aydın şəkildə optimal deyil.

x=y halını həll edək:

İddia: Biz $z$-dən çox M-əməliyyatı etməyəcəyik.

Sübut: $\text{cur}$-un $z$-in tam böləni olması üçün, $\text{cur}$-un $z$-in bütün ilkin faktorlarına sahib olması lazımdır. M-əməliyyatı etdikdə, $\text{cur}$-a ilkin faktorlar əlavə edirik, və $z$-də bir ilkin faktorun baş vermə sayları ilə $\text{cur}$-da eyni ilkin faktorun baş vermə sayları arasındakı maksimum fərq log(z)-dir, buna görə də $\text{cur}$-u $z$-in bütün ilkin faktorlarına sahib etmək üçün log(z)-dən çox M-əməliyyatı etməyəcəyik.

Bu, x=y üçün \text{cur} < z olduğu müddətcə M-əməliyyatlarını davam etdirə biləcəyimiz deməkdir və əgər $\text{cur}$-umuz $z$-dən böyük olarsa, $\text{cur}$-u \text{cur}\mod z-a bərabər edə bilərik, dəyəri \left \lfloor{\frac{\text{cur}}{z}} \right \rfloor (təkrarlanan S-əməliyyatları ilə), \text{cur}=0 olana qədər dayanırıq.

İndi tam problemi həll edək, əvvəlcə vəziyyəti ($i,j$) olaraq təyin edək, burada $i$ dəfə $x$-ə, $j$ dəfə $y$-ə vurmuşuq və $\text{cur}$ (n \cdot x^i \cdot y^j)\mod z-a bərabər olmalıdır (bu vəziyyətdə $\text{cur}$ dəyərinə \text{cur}[i][j] deyəcəyik).

Dinamik proqramlaşdırma yanaşmasını istifadə edə bilərik:

Əsas hal:

Keçid:

Cavab, \text{cur}[i][j] = 0 olduğu yerdə minimum \text{dp}[i][j] dəyəridir.

İndi $z$-dən çox M-əməliyyatı etməyəcəyimiz üçün, dp-nin mürəkkəbliyi \mathcal{O}(z^2)-dir, bu isə çox böyükdür.

x=y həllində dediyimiz kimi, $\text{cur}$-u $z$-in tam böləni etmək üçün log(z)-dən çox M-əməliyyatı etməyə ehtiyac yoxdur. Bu, həmişə 10^{11}-dən aşağı bir cavab alacağımız deməkdir. Əgər M-əməliyyatlarını istədiyimiz kimi etsək, maksimum cavabımız log(z) \cdot \left \lfloor{\frac{\max(x,y) \cdot (z-1)}{z}}\right \rfloor + log(z) \cdot (\log(z)+1) olacaq ki, bu da 10^{11}-dən aşağıdır.

Cavab həmişə 10^{11}-dən aşağı olduğuna görə, 5\cdot10^5 M-əməliyyatı etməyəcəyik, çünki onların dəyəri 10^{11}-dən böyük olacaq.

Bu, dp həllini \mathcal{O}(10^{11})-ə optimallaşdırır, $i,j$ üçün 5 \cdot 10^5 limitini qoyur, amma bu hələ də çox yavaşdır.

İndi ($i,j$) vəziyyətini nəzərdən keçirək, burada həm $i$, həm də $j$ log(z)-dən böyükdür, \text{cur}[i-1][j]=\text{cur}[i][j-1]=0 olması təmin edilir, və \min(\text{dp}[i-1][j],\text{dp}[i][j-1]) \le \text{dp}[i][j] olduğuna görə, ($i,j$) vəziyyətinə əhəmiyyət vermirik, çünki artıq daha yaxşı bir cavabımız var.

İndi əvvəlki dp-ni iki dəfə işlədə bilərik, birinci dəfə i \le log(z) , j \le 5 \cdot 10^5 ilə, ikinci dəfə isə i \le 5 \cdot 10^5 , j \le log(z) ilə.

Beləliklə, kodun ümumi mürəkkəbliyi \mathcal{O}(5 \cdot 10^5 \cdot \log(z))-dir ki, bu da keçmək üçün kifayət qədər sürətlidir.

#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
}