codeforce 839d.winter is here
2021-09-16 21:12
标签：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
文章标题：codeforce 839d.winter is here
文章链接：http://soscw.com/index.php/essay/107890.html