给你一个ｂ数组，让你求一个ａ数组；
要求，该数组的每一位都小于等于ｂ数组；
且这个ｂ数组的ｎ个数的gcd>=2
设f[i]表示gcd为i的a数组有多少个;
则从gcd大的开始,往gcd小的方向枚举gcd为i;
然后a的每个位置都可以为i的倍数;
则f[i] = a[1]/i * a[2] / i * a[3]/i … a[4]/i;
但是这里可能会重复算了gcd为i的倍数的情况;
则需要减掉f[j],这里j是i的倍数;
但是直接这样做是会超时的;
因为i要枚举n次,那个f[i]算的时候也要枚举n次;
复杂度早就到了N^2了;
ans在计算的时候,需要一些优化;
具体的;
用cnt[i]记录比i小的a数组元素有多少个;
则算出来a[]/i = 1的a[]有多少个,a[]/i = 2的a[]有多少个,a[]/i = 3的a[]有多少个…
a[]/i = 1 的个数 就为 cnt[i+i-1]-cnt[i-1],因为如果a的值在i..i+i-1之间的话,除i的结果都为1;
a[]/i = 2 的计算方法类似..cnt[2*i+i-1]-cnt[2*i-1];
这样,就不用循环n次了;
而只要找i的倍数就好了,依次算出来a[]/i = 1,a[]/i=2…的a[]各有多少个,然后把1^num1,2^num2,3^num3…都乘起来就可以了;
(用个快速幂)
其实关键就是快速幂吧,不然你也没办法快速算x^y,如果不知道快速幂,还是得一个一个乘,那样时间就没变了;
所以可以说这是一道快速幂用来优化的题目?
2
一开始想到了这种做法,但没有想到要怎么优化那个n次的循环.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
int T,n,a[N+10],cnt[N+10],f[N+10];
int ksm(int x,int y){
int ans = 1;
while (y){
if (y&1) ans = (ans * x)%MOD;
x = (x*x)%MOD;
y>>=1;
}
return ans;
}
main(){
//freopen("rush.txt","r",stdin);
scanf("%lld",&T);
for (int kk = 1;kk <= T;kk++){
memset(cnt,0,sizeof cnt);
scanf("%lld",&n);
int mi = INF;
for (int i = 1;i <= n;i++){
scanf("%lld",&a[i]);
mi = min(mi,a[i]);
cnt[a[i]]++;
}
for (int i = 1;i <= N;i++)
cnt[i] += cnt[i-1];
for (int i = mi;i >= 2;i--){
f[i] = 0;
if (cnt[i-1] > 0) continue;
int temp = 1;
for (int j = i;j <= N;j+=i){
int num = cnt[min(N,j+i-1)]-cnt[j-1];
int x = j/i;
temp = (temp*ksm(x,num))%MOD;
}
f[i] = temp;
}
int ans = 0;
for (int i = mi;i >= 2;i--){
for (int j = i + i;j <= mi;j+=i)
f[i] = (f[i]-f[j]+MOD)%MOD;
ans = (ans+f[i])%MOD;
}
printf("Case #%lld: %lld
",kk,ans);
}
return 0;
}