ABC112 D問題

多分行けそうと考察ふわふわで投げたら通ったので，反省を込めて

問題

やりたかったこと

求める$M=a_0+a_1+...+a_N$となる$a_{0toN}$の最大公約数なので，それを$b$としたとき
$$a_0\%b=0 \\
a_1\%b=0 \\
a_N\%b=0$$
なので$M$を割り切れる$b$で最大のものを求めたい的なことを考えていた．

投げたコード

template<class X> void is_prime( X n  , X m){
    if( n == 1 )
        cout << m << endl;
    else if( m % n == 0 ){
        cout << m / n << endl;
    }
    else{
        ll M = 0;
        int i = 2;  
        //ll lim = sqrt(m)+1;
        while( i * n <= m /*&& i < lim*/ ){
            if( m % i == 0){
                M = i;
            }
            i++;
        }
        if( M )
            cout << M << endl;
        else{
            if( m % 2 ){
                cout << 1 << endl;
            }
            else{
                if( m / n >= 2 ) 
                    cout << 2 << endl;
                else
                    cout << 1 << endl;
            }
        }
    }
}
int main(){
    ll n,m;
    cin >> n >> m;
    is_prime( n , m );
    ret 0;
}

素数判定のライブラリを100年ぶりに出したら無意味にtemplateとか使って笑いました
割り切れるときのペアになる数$\frac{m}{i}$を計算を代入している処理をしていないので，sqrtをちゃんと使うとWAになります．
テストケースが恐らく大きい$M$と小さい$N$の組み合わせがなかったのか，TLEすることなく通ってますがそういったのがあればTLEだと思います．ラッキー．

ゆっくり考えてわかったこと

$N=3，M=14$のとき
$$a_0+a_1+a_2=14$$
になる，$a_{0to2}$を考えるとき，$M$の約数$b$（最大とは限らない）と$c_{0to2}$を用いて，とする．
$$a_i=b・c_i$$
14の約数は1,2,7,14なので
$b=1$のとき，$a_i=1・c_i$
$b=2$のとき，$a_i=2・c_i$
$b=7$のとき，$a_i=7・c_i$
$b=14$のとき，$a_i=14・c_i$
$b$が7より大きいときは，全ての$c_i$が最小の1でも$a_0+a_1+a_2=14$を満たさなくなるのでは？🤔🤔🤔
つまり，$b・N>M$となる$b$はダメなのでは？🤔🤔🤔
ということは，$b・N<=M$の範囲で最大になる$b$を求めればいいのでは？🤔🤔🤔
$m/b$が$N$より大きいときは$c_i$に吸収させればいいのでは？🤔🤔🤔
約数は平方根まで求めて，ペアでとれば全て取れるのでは？🤔🤔🤔
という発想で書き直したのが次のコードです．

int main(){
    ll n,m;
    cin >> n >> m;
    ll lim = sqrt(m)+1;
    ll M = 0;   
    int i = 1;
    while( n * i <= m && i < lim ){
        if( !(m % i) ){
            M = max( M , ll(i));
            if( m >= n*(m/i) ){
                M = max( M , m/i );
            }
        }
        i++;
    }
    cout << M << endl;
    ret 0;
}

すごくシンプルになりましたね．
ACでした．
C問題を解けないので，そっちも明日とかにやっていきます．おやすみなさい．