题解：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;
}