HDU 6053 TrickGCD （莫比乌斯函数）

HDU 6053 TrickGCD （莫比乌斯函数）

Description

You are given an array A , and Zhu wants to know there are how many different array B1≤Bi≤AiFor each pair(l,r) (1≤l≤r≤n) , gcd(bl,bl+1...br)≥2

Input

The first line is an integer T(1≤T≤10)Each test case begins with an integer number n describe the size of array AThen a line contains n numbers describe each element of AYou can assume that 1≤n,Ai≤105

Output

For the kth test case , first output “Case #k: ” , then output an integer as answer in a single line . because the answer may be large , so you are only need to output answer mod 109+7

Sample Input

144 4 4 4

Sample Output

Case #1: 17

题意

给出数组 A ，问有多个种 B

思路

针对条件，我们可以枚举 gcd ，显然对于每一个素因子 i 在范围 [i,j] 下共有 ji 个数可以整除它，假设 A 中共有 cnt 个数字处于 [j,j+i−1] 这个范围内，这也就相当于有 cnt 个位置的数可以在 ji 个因子中随意变动，共有 (ji)cnt 种方案，而对于每一个因子，其结果为 ∑i|j(ji)cnt

最终通过容斥或者莫比乌斯去掉重复部分即可。

AC 代码

#include #include #include #include #include #includeusing namespace std ;#define inf 0x3f3f3ftypedef __int64 LL;const int maxn = 1e5+10;const int mod = 1e9+7;LL mu[maxn];LL sum[maxn<<1];LL cnt[maxn<<1];void init(){ mu[1]=1; for(int i=1; i>=1; } return res;}int main(){ ios::sync_with_stdio(false); init(); int T; cin>>T; for(int ti=1; ti<=T; ti++) { int n,minn=inf; memset(cnt,0,sizeof(cnt)); cin>>n; for(int i=0; i>x; cnt[x]++; minn=min(minn,x); } LL ans=0; for(int i=1; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。