CF915G Coprime Arrays

    • 34通过
    • 53提交
  • 题目来源 CodeForces 915G
  • 评测方式 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类违反进行处理。