Background

dts的一个脑洞第3期

Description

已知(a,b)=1
计算[a/b]+[2a/b]+⋯+[(b-1)a/b]的值
请回答表达式的值对k取模的结果，k将在输入中给出，数据保证k是一个质数。

Format

Input

输入包含多组数据，请处理到文件结束
每组数据1行，包含a,b,k三个数

Output

对于每组数据，输出一行一个数，表达式的值对k取模的结果

Sample 1

Input

2 3 10007

Output

1

Limitation

1s, 4194304KiB for each test case.

Hint

每组输入不超过10^5组数据
对于100%的数据，每组n,m,k满足，1≤a≤2^60,1≤b≤2^60,k≤2^30

C++ Code

#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    ll ny(ll x,ll key)
    {
        if (x==1)
            return 1;
        else
            return -(key/x)*ny(key%x,key)%key;
    }
    
    ll a,b,key;
    
    void main()
    {
        while (~scanf("%lld%lld%lld",&a,&b,&key))
        {
            ll p=ny(2,key);
            if (p<0)
                p+=((key-p)/key)*key;
            ll ans=(p*(((a-1)%key)*((b-1)%key)%key))%key;
            printf("%lld\n",ans);
        }
    }
};

int main()
{
    dts::main();
}

Source

Vijos Original