模拟赛题目，讲评没听懂

重要的事情说三遍：

提供思路就好

提供思路就好

提供思路就好

现代人 fraction

题目背景

远古人的科技力大幅度进步，学习了分数概念（？。因此我们用现代人称呼他们（确信。

为了确认他们的智力能否达到现代人水准，小 C 考了他们一个问题。

题目描述

给定 $n,k,p$，并以此生成了若干个分数： $\frac{1}{p^k},\frac{2}{p^k},\dots,\frac{n}{p^k}$

远古人需要把这些分数约分为最简分数，一个分数

$\frac{p}{q}$ 被称为最简分数当且仅当 $\gcd(p,q)=1$。

记第 $i$ 个分数约分后 $\frac{a_i}{b_i}$，你需要求出 $\sum a_i$，即所有 $a_i$ 的和。

输入格式

一行三个整数 $n,k,p$。

输出格式

一行一个正整数，表示答案。

同样的，请选择合适的数据类型储存答案。

样例 #1

样例输入 #1

3 1 2

样例输出 #1

5

提示

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq n,k,p\leq 10^9$，各测试点的具体约束如下：

• 测试点 $1\sim 4$：$n,k,p\leq 10^3$。
• 测试点 $5\sim 6$：$k=0$。
• 测试点 $7\sim 10$：无额外约束。

【样例 1 解释】

生成的分数组如下：$\frac{1}{2},\frac{2}{2},\frac{3}{2}$。

经过约分后为：$\frac{1}{2},\frac{1}{1},\frac{3}{2}$。

答案为 $1+1+3=5$。