Online Judge：Hdu6053
Label：容斥，前缀和
题面：
题目描述
给你一个长度为(N)的序列A，现在让你构造一个长度同样为(N)的序列B，并满足如下条件，问有多少种方案数？答案对(1e9+7)取模。
-
(1≤Bi≤Ai)
-
对于任意(l,r) ((1≤l≤r≤N))，有(gcd(b_l,b_{l+1}...b_r)>=2)
输入
The first line is an integer T(1≤T≤10) describe the number of test cases.
Each test case begins with an integer number n describe the size of array A.
Then a line contains n numbers describe each element of A
You can assume that (1≤n,Ai≤10^5)
输出
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 (10^9+7)
样例
Input
1
4
4 4 4 4
Output
Case #1: 17
题解
一、暴力做法：(O(N cdot(ln(N)+N)))
这题的暴力做法很容易想到，直接枚举(gcd)，统计该值对答案的贡献。对于序列A中的第i个数，此时他可取的数字有(Ai/gcd)种，则此时整个序列的方案数为(Ans=A_1/gcd *A_2/gcd cdot...* A_N/gcd)。
当然还需要容斥，我们从大到小枚举这个(gcd)，然后再减去(gcd)的倍数对答案的贡献即可。
二、AC做法：(O(N cdot ln(N)))
上面做法的瓶颈在于直接O(N)地枚举整个A序列来求该(gcd)对答案的贡献。
仍然是枚举(gcd)，发现([i cdot gcd，(i+1) cdot gcd-1])这个区间内的数在此时的贡献都是(i)。想到直接枚举(gcd)的倍数即可，而查一段区间内的数字个数可以用前缀和完成（因为序列数字的上限只有1e5）。对于每个(gcd)，之前的暴力做法是全部累乘，而这里用一下快速幂就好了。
完整代码如下：
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N=1e5+10;
int n,a[N],f[N];
int dp[N];
int ksm(int a,int d){
int res=1;
while(d){
if(d&1)res=res*a%mod;
a=a*a%mod;d>>=1;
}
return res;
}
signed main(){
int T,cas=0;scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
memset(f,0,sizeof(f));
memset(dp,0,sizeof(dp));
int ma=0,ans=0;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),ma=max(ma,a[i]),f[a[i]]++;
for(int i=1;i<=ma;i++)f[i]+=f[i-1];
for(int i=ma;i>=2;i--){
int cur=1;
for(int ti=0,j=0;j<=ma;ti++,j+=i){
int num=f[min(j+i-1,ma)];
if(j!=0)num-=f[j-1];
cur=cur*ksm(ti,num)%mod;
}
for(int j=i+i;j<=ma;j+=i)cur=(cur-dp[j]+mod)%mod;
ans=(ans+(dp[i]=cur))%mod;
}
printf("Case #%lld: %lld
",++cas,(ans+mod)%mod);
}
}