# CF915G Coprime Arrays

• 34通过
• 53提交
• 题目来源
• 评测方式 RemoteJudge
• 标签 前缀和 差分 数论,数学
• 难度 省选/NOI-
• 时空限制 3500ms / 256MB
• 提示：收藏到任务计划后，可在首页查看。

## 题意翻译

#### 题意：

我们称一个大小为 $n$ 的数组 $a$ 互质，当且仅当 $gcd(a_1,a_2,\cdots,a_n)=1$，$gcd$ 是最大公约数的意思。

给定 $n,k$，对于每个 $i$ $(1\le i\le k)$，你都需要确定这样的数组的个数——长度为 $n$ 的数组 $a$ ，满足对每个 $j$ $(1\le j\le n)$，都有 $1\le a_j\le k$ 的个数。

答案可能非常大，请对 $10^9+7$ 取模。

#### 输入格式：

只有一行，两个数 $n,k$ $(1\le n,k\le 2\cdot10^6)$，分别表示数组的大小和数组元素大小的上限。

#### 输出格式：

为了降低输出的时间，你需要对输出进行如下处理：

把 $i$ 的答案（对 $10^9+7$ 取模后）记作 $b_i$。你需要输出 $\sum_{i=1}^{n} (b_i\oplus i)$，再对 $10^9+7$ 取模。

这里 $\oplus$ 表示按位异或，在 c++ 和 Java 中写作 ^，在 Pascal 中写作 xor

#### 说明：

第一个样例的说明：

因为互质数组的数量比较多，我们只列出不互质的：

当 $i=1$ 时，唯一的数组就是互质的，$b_1=1$。

当 $i=2$ 时，数组 $[2,2,2]$ 不是互质的，$b_2=7$。

当 $i=3$ 时，数组 $[2,2,2],[3,3,3]$ 不是互质的，$b_3=25$。

当 $i=4$ 时，数组 $[2,2,2],[3,3,3],[2,2,4],[2,4,2],[2,4,4],[4,2,2],[4,2,4],[4,4,2],[4,4,4]$ 不是互质的，$b_4=55$。

Translated by 小粉兔

## 题目描述

Let's call an array $a$ of size $n$ coprime iff $gcd(a_{1},a_{2},...,a_{n})=1$ , where $gcd$ is the greatest common divisor of the arguments.

You are given two numbers $n$ and $k$ . For each $i$ ( $1<=i<=k$ ) you have to determine the number of coprime arrays $a$ of size $n$ such that for every $j$ ( $1<=j<=n$ ) $1<=a_{j}<=i$ . Since the answers can be very large, you have to calculate them modulo $10^{9}+7$ .

## 输入输出格式

输入格式：

The first line contains two integers $n$ and $k$ ( $1<=n,k<=2·10^{6}$ ) — the size of the desired arrays and the maximum upper bound on elements, respectively.

输出格式：

Since printing $2·10^{6}$ numbers may take a lot of time, you have to output the answer in such a way:

Let $b_{i}$ be the number of coprime arrays with elements in range $[1,i]$ , taken modulo $10^{9}+7$ . You have to print , taken modulo $10^{9}+7$ . Here denotes bitwise xor operation (^ in C++ or Java, xor in Pascal).

输入样例#1： 复制
3 4

输出样例#1： 复制
82

输入样例#2： 复制
2000000 8

输出样例#2： 复制
339310063

## 说明

Explanation of the example:

Since the number of coprime arrays is large, we will list the arrays that are non-coprime, but contain only elements in range $[1,i]$ :

For $i=1$ , the only array is coprime. $b_{1}=1$ .

For $i=2$ , array $[2,2,2]$ is not coprime. $b_{2}=7$ .

For $i=3$ , arrays $[2,2,2]$ and $[3,3,3]$ are not coprime. $b_{3}=25$ .

For $i=4$ , arrays $[2,2,2]$ , $[3,3,3]$ , $[2,2,4]$ , $[2,4,2]$ , $[2,4,4]$ , $[4,2,2]$ , $[4,2,4]$ , $[4,4,2]$ and $[4,4,4]$ are not coprime. $b_{4}=55$ .

提示
标程仅供做题后或实在无思路时参考。
请自觉、自律地使用该功能并请对自己的学习负责。
如果发现恶意抄袭标程，将按照I类违反进行处理。