首页 > 其他 > 详细

UESTC - 1172 三句话题意

时间:2018-03-06 23:55:20      阅读:338      评论:0      收藏:0      [点我收藏+]

题目链接

记一个集合的gcd为该集合内所有数的最大公约数, 
求一个给定集合的非空子集的gcd的k次方的期望~

Input

第一行有一个数t,表示数据组数 
接下去每组数据两行,第一行两个数n,k(0 <n,k<=10^6),表示该集合有n个数字。 <br="">第二行有n个数ai(0<=ai<=2000000)代表该集合内的所有元素。

Output

每组数据输出一行,为期望乘上2^n-1,之后取模10000007的结果。

Sample Input

2
5 1
1 2 3 4 5
3 2
2 3 6

Sample Output

42
64

Hint

样例2中gcd为1的非空子集集有{2,3},{2,3,6}两个, 
2的有{2},{2,6}两个,3的有{3},{3,6}两个,6的有{6}一个。 
所以期望是(2*1^2+2*22+2*3^2+1*42)/7=64/7。

 

题解 

  这题主要是得求出对应gcd值下的子集个数。对于gcd值,我们能够指定一个值x,那么x的倍数都可以组成任意子集。所以第一步统计每个数字的个数,然后假设当前gcd=x,那么此时的集合内元素数应该为x的倍数的个数。可为了求出所有的值,这里存在重复的,所以我们需要减去一部分,如果从大往小执行,这样减去的就是重复的部分。

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 2e6+5;
const int mod = 10000007;
int cnt[maxn],res[maxn];
LL num[maxn];
LL qpow(LL a,LL b){
    LL res=1;
    while(b){
        if(b&1) res = (res*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return res%mod;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,x,k,maxx=-1;
        memset(cnt,0,sizeof(cnt));
        memset(res,0,sizeof(res));
        memset(num,0,sizeof(num));
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++){
            scanf("%d",&x);
            maxx=max(maxx,x);
            cnt[x]++;
        }

        for(int i=1;i<=maxx;i++){
            for(int j=1;j*i<=maxx;j++){
                res[i] += cnt[i*j];
            }
        }
        for(int i=1;i<=maxx;i++)
            num[i]=(qpow(2,res[i])-1+mod)%mod;
        for(int i=maxx;i>=1;i--){
            for(int j=2;j*i<=maxx;j++){
                num[i] = (num[i]-num[j*i]+mod)%mod;
            }
        }

        LL ans = 0;
        for(int i=1;i<=maxx;i++){
            ans = (ans+num[i]*qpow(i,k))%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

UESTC - 1172 三句话题意

原文:https://www.cnblogs.com/fht-litost/p/8519705.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!