bzoj 3560 DZY Loves Math V - 线性筛 - 数论 - 扩展欧几里得算法

给定n个正整数a1,a2,…,an,求

的值(答案模10^9+7)。

Input

第一行一个正整数n。

接下来n行,每行一个正整数,分别为a1,a2,…,an。

Output

仅一行答案。

Sample Input

3
6
10
15

Sample Output

1595

Hint

1<=n<=10^5,1<=ai<=10^7。共3组数据。



  题目大意 (题目过于简洁,完全不需要大意)

  题目虽然很简洁,但是处处挖着坑等你跳。

  原计划两个小时把今天讲的例题A完,实际上两个小时都被这道题坑走了(懒惰于重新推公式的下场。。。)

  //假设读者知道什么是积性函数以及欧拉函数的积性

  欧拉函数的积性可以表现在这种形式(里面p + 下标都表示互不相同的质数):

  所以,我们可以把每个不同的素数分开进行计算贡献,然后再求积(因为我们是把每个像上述形式拆分求phi值,所以是求积)。

  于是我们成功得到了某个更长的式子:(其中b(p)i表示ai中质因子p的指数)

  由于欧拉函数在此不好运用某些套路快速求结果,所以考虑运用欧拉函数神奇的性质将其拆开。我们知道有关欧拉函数有(同样,p是质数)

  虽然当指数为0的时候为特殊情况,但是可以加点黑科技是它不是那么地特殊:

  是滴,多加了一个1/p就解决了问题。现在继续化简:

  此时计算的时间复杂度能够接受。但是由于在模意义下做除法需要乘逆元,由于p是小于1e7的质数,所以一定和1e9 + 7互质,所以逆元一定存在。

  关于这道题还有很神奇的东西,存有哪些不同的素数用STL(Standard Templates Library Sometimes/Standard TLE/MLE Library),然而MLE。。。求解释。。。好像和理论算的不太一样。。

  所以就用一个黑科技。用pair的第一位存是什么素数,第二位存指数。然后sort一下,就可以AC了。

Code

  1 /**
  2  * bzoj
  3  * Problem#3560
  4  * Accepted
  5  * Time: 1276ms
  6  * Memory: 7940k
  7  */
  8 #include <bits/stdc++.h>
  9 #ifndef WIN32
 10 #define Auto "%lld"
 11 #else
 12 #define Auto "%I64d"
 13 #endif
 14 using namespace std;
 15 typedef bool boolean;
 16 #define smax(a, b) a = max(a, b)
 17 #define LL long long
 18
 19 const int moder = 1e9 + 7;
 20 LL mpow(LL a, LL pos) {
 21     if(pos == 0)    return 1;
 22     if(pos == 1)    return a;
 23     LL temp = mpow(a, pos >> 1);
 24     temp = (temp * temp) % moder;
 25     if(pos & 1)    temp = (temp * a) % moder;
 26     return temp;
 27 }
 28
 29 void exgcd(LL a, LL b, LL& d, LL& x, LL& y) {
 30     if(!b) {
 31         d = a;
 32         x = 1, y = 0;
 33     } else {
 34         exgcd(b, a % b, d, y, x);
 35         y -= (a / b) * x;
 36     }
 37 }
 38
 39 int inv(int a, int moder) {
 40     LL d, x, y;
 41     exgcd(a, moder, d, x, y);
 42     return (x < 0) ? (x + moder) : (x);
 43 }
 44
 45 const int limit = 3500;
 46 int num = 0;
 47 int prime[1000];
 48 boolean vis[limit + 1];
 49 inline void Euler() {
 50     for(int i = 2; i <= limit; i++) {
 51         if(!vis[i])    prime[num++] = i;
 52         for(int j = 0; j < num && i * prime[j] <= limit; j++) {
 53             vis[i * prime[j]] = true;
 54             if((i % prime[j] == 0))
 55                 break;
 56         }
 57     }
 58 }
 59
 60 int n;
 61 int* arr;
 62 int cnt = 0;
 63 pair<int, int> ds[800005];
 64 inline void init() {
 65     scanf("%d", &n);
 66     arr = new int[(n + 1)];
 67     for(int i = 1; i <= n; i++) {
 68         scanf("%d", arr + i);
 69     }
 70 }
 71
 72 LL getSum(int p, int c) {
 73     LL a = (mpow(p, c + 1) - 1);
 74     LL b = inv(p - 1, moder);
 75     return (a * b) % moder;
 76 }
 77
 78 LL res = 1;
 79 inline void solve() {
 80     for(int i = 1, x; i <= n; i++) {
 81         x = arr[i];
 82         for(int j = 0; prime[j] * prime[j] <= x && arr[i] > 1; j++) {
 83             if((arr[i] % prime[j]) == 0) {
 84                 ds[cnt].first = prime[j], ds[cnt].second = 0;
 85                 while((arr[i] % prime[j]) == 0)
 86                     arr[i] /= prime[j], ds[cnt].second++;
 87                 cnt++;
 88             }
 89         }
 90         if(arr[i] > 1)
 91             ds[cnt].first = arr[i], ds[cnt++].second = 1;
 92      }
 93     sort(ds, ds + cnt);
 94
 95     int p, c;
 96     for(int id = 0; id < cnt; ) {
 97         p = ds[id].first;
 98         LL P = 1;
 99         for(int i = id; (id < cnt && ds[i].first == ds[id].first) ? (true) : (id = i, false); i++) {
100             c = ds[i].second;
101             P = (P * getSum(p, c)) % moder;
102         }
103         P = ((P * (p - 1) + 1) % moder) * inv(p, moder) % moder;
104         res = (res * P) % moder;
105     }
106     printf(Auto, res);
107 }
108
109 int main() {
110     Euler();
111     init();
112     solve();
113     return 0;
114 }
时间: 08-16

bzoj 3560 DZY Loves Math V - 线性筛 - 数论 - 扩展欧几里得算法的相关文章

bzoj 3309 DZY Loves Math - 莫比乌斯反演 - 线性筛

对于正整数n,定义f(n)为n所含质因子的最大幂指数.例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0. 给定正整数a,b,求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b). Input 第一行一个数T,表示询问数. 接下来T行,每行两个数a,b,表示一个询问. Output 对于每一个询问,输出一行一个非负整数作为回答. Sample Input 4 7558588 9653114 6514903 445

BZOJ3560: DZY Loves Math V

虽然不是很神的题,不过拿短代码搞到rank1了那么纪念下. 先观察样例. 6=2*3; 10=2*5; 15=3*5; 对应答案:1595=5*11*29: 其中: 5=((1+2)*(1+2)*1*(2-1)+1)/2 11=((1+3)*1*(1+3)*(3-1)+1)/3 29=(1*(1+5)*(1+5)*(5-1)+1)/5 证明不写了……自行领会精神. 就是对每个n因数分解后对每个p分开搞搞. [代码](话说好不容易才发现插入代码这功能) 1 #include<cstdio> 2

【BZOJ】3309: DZY Loves Math 莫比乌斯反演优化

3309: DZY Loves Math Description 对于正整数n,定义f(n)为n所含质因子的最大幂指数.例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0. 给定正整数a,b,求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b). Input 第一行一个数T,表示询问数. 接下来T行,每行两个数a,b,表示一个询问. Output 对于每一个询问,输出一行一个非负整数作为回答. Sample In

[BZOJ3568]DZY Loves Math VII

本人BZOJ的处女作. 这题题面还是蛮有趣的吧. 然后三个问题都蛮有意思的. 要保证正确性,出数据还是异常蛋疼啊. 本来各出三题的.但是考虑到是OJ上的题,就搞在一起了.这样代码量就会比较大. [BZOJ3568]DZY Loves Math VII,布布扣,bubuko.com

【莫比乌斯反演】BZOJ3309 DZY Loves Math

Description 对于正整数n,定义f(n)为n所含质因子的最大幂指数.例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0. 给定正整数a,b,求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b).T<=1e4; a,b<=1e7. Solution 一开始没仔细看数据范围然后打了一个每个询问O(n)的,当然T了 (盗一张图) 一开始我按照第二行的做的,里层外层循环都和ab有关,每一层都要sqrt(n)

Bzoj3481 DZY Loves Math III

Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 310  Solved: 65 Description Input Output Sample Input 3 1 2 3 2 4 2 Sample Output 6 HINT 1<=N<=10,0<=Qi<=10^18,1<=Pi<=10^18,P>=2 本题仅四组数据. Source By Jc 数学问题 欧拉函数 Miller-Rabin Pollard-rho 花了

BZOJ 2693: jzptab [莫比乌斯反演 线性筛]

2693: jzptab Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 1194  Solved: 455[Submit][Status][Discuss] Description Input 一个正整数T表示数据组数 接下来T行 每行两个正整数 表示N.M Output T行 每行一个整数 表示第i组数据的结果 Sample Input 1 4 5 Sample Output 122 HINT T <= 10000 N, M<=1000000

Codeforces 444A DZY Loves Physics(图论)

题目链接:Codeforces 444A DZY Loves Physics 题目大意:给出一张图,图中的每个节点,每条边都有一个权值,现在有从中挑出一张子图,要求子图联通,并且被选中的任意两点,如果存在边,则一定要被选中.问说点的权值和/边的权值和最大是多少. 解题思路:是图论中的一个结论,最多两个节点,所以枚举两条边就可以了.我简单的推了一下,2个点的情况肯定比3个点的优. 假设有3个点a,b,c,权值分别为A,B,C 现a-b,b-c边的权值分别为u,v 那么对于两点的情况有A+Bu,B+

Hdoj 5195 DZY Loves Topological Sorting 【拓扑】+【线段树】

DZY Loves Topological Sorting Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 922 Accepted Submission(s): 269 Problem Description A topological sort or topological ordering of a directed graph i