U370070 可爱的数组

## 好不容易有个 idea，结果。。。[1](https://loj.ac/p/6491) [2](https://www.luogu.com.cn/problem/AT_abc162_e) xbx 又喜欢上了数组

给定正整数 $n,m,p$，求所有项都在 $1\sim n$ 里的 $m$ 项数列的 $\gcd$ 之和，答案对 $p$ 取模 ### 形式化描述 给定正整数 $n,m,p$，求 $\newcommand\d[1]{\sum\limits_{a_{#1}=1}^n}\d{1}\d{2}\dots\d{m} \gcd(a_1,a_2,\dots,a_m)$，答案对 $p$ 取模

一行三个正整数 $n,m,p$，用空格隔开

一行一个正整数，表示你的答案

$1 \le n \le 5 \times 10^9,1 \le m \le 10^{10^7},1 \le p \le 10^{15}$，不保证 $p$ 是素数 目前 std 时间复杂度约为 $\Theta(n^{\frac{3}{4}})$，谁来暴打一下 std？ **目前 $\tt 5s$ 在 Bingxiu 的计算机上能跑到 $10^{10}$，然而洛谷上只能跑到 $5 \times 10^9$** 这里提供 std，希望有人 hack 或暴打： ```cpp //莫比乌斯反演，sum d=1~n(mu(d) sum k=1~n/d(k(n/kd)^m)) #include using namespace std; typedef long long ll; typedef __int128_t li; ll n,m,p,k,f[346419],x,ans,b;//b=floor(n^(3/4)) #define ind(_) (x=(_),f[x>1)*a%p:w(a*a%p,b>>1);} inline void init(){//(n/k)^m for(ll l=1;l