По поводу задачи C. http://e-maxx.ru/algo/diofant_2_equation Утверждается, что если c%g==0, то уравнение имеет решение, в противном случае не имеет. Доказательство следует из очевидного факта, что линейная комбинация двух чисел по-прежнему должна делиться на их общий делитель. Объясните, пожалуйста, почему она по-прежнему должна делиться на g?

Посмотрел решения участников по E, но так и не понял. Кто может дать идею?

How to solve problem D?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
int32_t main(){
    string st;cin>>st;
    int n=st.size();
    int m=1e9+9;
    int p=1;
    int mx=5*(1e6)+1;
    vector<int>pw(mx),pre(n),suf(n+1,0),dp(n+1,0);
    for(int i=0;i<mx;i++){
        pw[i]=p;
        p=(p*53)%m;
    }
    for(int i=0;i<n;i++){
        pre[i]=(pw[i]*st[i])%m;
        if(i!=0) pre[i]=(pre[i-1]+pre[i])%m;
    }
    // string r=st;
    for(int i=n-1;i>=0;i--){
        suf[i]=(pw[n-i-1]*st[i])%m;
        suf[i]=(suf[i]+suf[i+1])%m;
    }
    dp[1]=1;
    int ans=1;
    for(int i=1;i<n;i++){
        ll tm=(suf[0]-suf[i+1]+m)%m;
        ll tm2=(pre[i]*pw[n-i-1])%m;
        if(tm==tm2) {
            dp[i+1]=dp[(i+1)/2]+1;
        }
        ans+=dp[i+1];
    }

    cout<<ans<<endl;
    
}