codeforce 839d.winter is here

2021-09-16 21:12

阅读:654

标签:force   自己   log   std   枚举   价值   can   div   c代码   题意:如果一个子序列的GCD为1,那么这个子序列的价值为0,否则子序列价值为子序列长度*子序列GCD 给出n个数,求这n个数所有子序列的价值和 题解:首先得想到去处理量比较少的数据的贡献,这里处理每个gcd的贡献。我们定义f(i)为gcd==i的倍数时的贡献,那么f(i)=c(0,n)*0+c(1,n)*1+...c(n,n)*n ,这里的n为能够整除i的数的个数。 然后结合c(1,n)+c(2,n)+....c(n,n)=2^n这个可以推出f(i)=n*2^(n-1)。然后倒着容斥一下(虽然自己看着别人的代码看了半天,这里还是装逼带过吧23333)。 ac代码: #include #define mod 1000000007 #define LL long long LL cnt[1000005], sum[1000005]; LL Pow(LL a, LL b) { LL now; now = 1; while(b) { if(b%2) now = now*a%mod; a = a*a%mod; b /= 2; } return now; } int main(void) { LL ans, i, j, n, x; scanf("%lld", &n); for(i=1;i=2;i--) { x = 0; for(j=i;j


评论


亲,登录后才可以留言!