TrickGCD
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 2855 Accepted Submission(s): 1075
Problem Description
You are given an array
A
, and Zhu wants to know there are how many different array
B
satisfy the following conditions?
*
1≤Bi≤Ai
* For 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
) 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≤105
Output
For the
k
th 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
1
4
4 4 4 4
Sample Output
Case #1: 17
Source
2017 Multi-University Training Contest - Team 2
题意：
给你a数列，求出gcd>=2的b数列数量，b[i]每个数都小于等于a[i]。
POINT：
枚举gcd，然后容斥。记录a[i]数组的数量，然后枚举。
比如枚举2，就看a[i]里有多少2和3。具体看代码。
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
using namespace std;
#define LL long long
const int N = 1e5;
const LL p= 1e9+7;
LL pre[N+4],sum[N+4];
LL num[N+4];
LL qkm(LL base,LL mi)
{
base%=p;
LL ans=1;
while(mi)
{
if(mi&1) ans=ans*base;
base*=base;
mi>>=1;
base%=p;
ans%=p;
}
return ans;
}
int main()
{
int T;
int k=0;
scanf("%d",&T);
while(T--)
{
memset(pre,0,sizeof pre);
memset(num,0,sizeof num);
memset(sum,0,sizeof sum);
int n,o;
scanf("%d",&n);
int maxx=0;
for(int i=1;i<=n;i++)
scanf("%d",&o),pre[o]++,maxx=max(maxx,o);
for(int i=1;i<=N;i++) sum[i]=sum[i-1]+pre[i];
int flag=1;
for(int i=2;i<=N;i++)
{
if(!flag) break;
else
{
num[i]=1;
for(int j=0;j<=maxx;j+=i)
{
int a=j/i;
LL b=sum[min(j+i-1,N)]-sum[max(j-1,0)];
if(!a&&b)
{
num[i]=0;
flag=0;
break;
}
num[i]=(num[i]*qkm(a,b))%p;
}
}
}
for(int i=N;i>=2;i--)
{
for(int j=2*i;j<=N;j+=i)
{
num[i]-=num[j];
num[i]=(num[i]+p)%p;
}
}
LL ans=0;
for(int i=2;i<=N;i++)
{
(ans+=num[i])%=p;
}
printf("Case #%d: %lld\n",++k,ans);
}
}
