题解：P9441 [ICPC2021 WF] Fair Division

题目链接

• 洛谷 P9441 [ICPC2021 WF] Fair Division

解题思路

推导公式

设第 $x$ 个人拿到的钱为 $F(x)$ 。

注意到 $\displaystyle F(x)=m\sum_{i=0}^{\infty}(1-f)^{in+x}f$ ，设 $\displaystyle\sum_{i=0}^{\infty}(1-f)^{in+x}$ 为 $S$。

则 $S-(1-f)^nS=(1-f)^x$，可得 $S=\dfrac{(1-f)^x}{1-(1-f)^n}$。

所以 $F(x)=\dfrac{(1-f)^x}{1-(1-f)^n}fm$。

设 $t=(1-f)=\dfrac{r}{q}$。

则 $F(x)=\dfrac{t^x}{1-t^n}(1-t)m=\dfrac{(\dfrac{r}{q})^x(\dfrac{q-r}{q})m}{1-(\dfrac{r}{q})^n}$。

上下同乘以 $q^n$ 并化简得到 $F(x)=\dfrac{r^xq^{n-x-1}(q-r)m}{q^n-r^n}$。

证明互质

对于 $q$ 的任何一个因数 $a$，可得 $a$ 也是 $q^n$ 的因数，而 $r$ 与 $q$ 互质，故 $a$ 不是 $r$ 的因数，所以 $a$ 不是 $q^n-r^n$ 的因数，但因为 $a$ 是 $r^xq^{n-x-1}$ 的因数，所以 $r^xq^{n-x-1}$ 与 $q^n-r^n$ 互质。证毕。

继续推导

因此，若要使 $F(x)$ 为整数，$q^n-r^n$ 必须能够整除 $(q-r)m$。

所以将 $q^n-r^n$ 展开，得到 $\displaystyle(q-r)\sum_{i=0}^{n}{r^{i}q^{n-i-1}}$。

注意到 $(q-r)$ 已经出现了两次，所以不做考虑，只需要验证 $\displaystyle\sum_{i=0}^{n}{r^{i}q^{n-i-1}}$ 能否整除 $m$ 即可。

因为 $n\ge6$，所以可以直接枚举 $r$ 和 $q$ 的值。

同时 $q^{n-1}$ 需要不大于 $m$，数据范围实际上并不大，只需要用 __int128 确保在运算过程中不会超出范围即可。

参考代码

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

static const int INF = 2e18;
int n , m;

int mul(int a , int b)
{
    return min(((__int128_t)a) * b , (__int128_t)INF);
}

int fpow(__int128 a , int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = mul(res , a);
        }
        a = mul(a , a);
        b >>= 1;
    }
    return res;
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int q = 2 ; fpow(q , n - 1) <= m && fpow(q , n - 1) != 2147483647 ; q++)
    {
        for(int r = 1 ; r < q ; r++)
        {
            int num = 0;
            for(int i = 0 ; i < n ; i++)
            {
                num = min(num + mul(fpow(r , i) , fpow(q , n - i - 1)) , INF);
            }
            if(m % num == 0)
            {
                cout << q - r << " " << q << '\n';
                return 0;
            }
        }
    }
    cout << "impossible" << '\n';
    return 0;
}