原题链接

题解

1.由于是除二操作，所以最后的平均数一定能表示成 \(k_1\cdot \frac{1}{2^{i_1}}+...+k_t\cdot \frac{1}{2^{i_t}}\) 的形式

2.最小的 \(\frac{1}{2^i}\) 由于没有往下再分，所以数量一定是偶数，把他们的数量除二加到 \(\frac{1}{2^{i-1}}\) 上，此时 \(i-1\) 就变最小的了

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

void solve()
{
    ll n,m;
    cin>>n>>m;

    ll tem=m;

    n%=m;
    if(n==0)
    {
        cout<<0<<'\n';
        return;
    }

    ll g=__gcd(n,m);
    n/=g;
    m/=g;
    ll tem1=log2(m);
    if((1<<tem1)!=m)
    {
        cout<<-1<<'\n';
        return;
    }

    map<ll,ll> rec;

    while(n)
    {
        ll c=log2(n);
        ll v=(1LL<<c);
        rec[c]=n/v*tem;
        n%=v;
    }

    ll cnt=0;
    for(auto it:rec)
    {
        cnt+=it.second/2;
        if((1LL<<(it.first+1))<m) rec[it.first+1]+=it.second/2;
    }

    cout<<cnt<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}