Description

聰明的0v0正在學(xué)習(xí)莫比烏斯反演。
她看到了這樣的一道題：有n*m個人站成了一個n*m的方陣……
剩下的題面，聰明的0v0不記得了。但是，她通過自己高超的數(shù)論技巧，給出了一個轉(zhuǎn)化后的模型：給出n和m，求

聰明的0v0當(dāng)然知道怎么做了，但是她想考考你。

Input

一行三個正整數(shù)n，m，p。

Output

一行一個非負整數(shù)，設(shè)答案為x，輸出x mod p。

Sample Input

1 2 998244353

Sample Output

2

Data Constraint

30% n,m<=2000 p=998244353。
30% n*m<=10^9 n,m<=10^5 p為質(zhì)數(shù)
20% n,m<=10^6 p為質(zhì)數(shù)
20% n,m<=10^7 p為合數(shù)
對于所有數(shù)據(jù)，保證p<=10^9

Solution

• 這題怎么做呢？莫比烏斯反演？的確可以。

• 但是打表后發(fā)現(xiàn)——最優(yōu)做法是：輸出 n?m?mod?p 即可。

• 什么？這也行?

• 其實，原式的物理意義，就是從坐標原點 （0,0），用每一種合法的斜率，

• 穿過坐標 [1—n,1—m] 的方陣中的整點的個數(shù)，

• 總數(shù)即 n?m 。

Code

#include<cstdio> using namespace std; int n,m,p; int main() {scanf("%d%d%d",&n,&m,&p);printf("%d",(long long)n*m%p);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5425. 【NOIP2017提高A组集训10.25】数论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。