我是靠谱客的博主 成就果汁,最近开发中收集的这篇文章主要介绍codeforces900D 2100分莫比乌斯反演题目传送门题意:题解:感受:代码:,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目传送门

题意:

正整数序列 dpi{150}a ,序列的 gcd 是 x ,并且序列之和是 y 。

问这样的序列个数,答案取模。

数据范围:1 leqslant x ;,; y leqslant 10^9 。

题解:

容易发现存在这样的序列等价于 x mid y 。

简化一下题意,这样的序列是 gcd 是 1 ,并且序列之和是 frac{y}{x} 。

gcd 是 1 ,并且序列之和是 x 的函数 f(x) 是不好求的。

序列之和是 x 的函数 g(x) 是很好求的。 

这样就考虑莫比乌斯反演了。

想一想会发现, g(x) = sum_{dmid x}f(frac{x}{d}) 。

反演一下,f(x) = sum_{dmid x} mu(d) g(frac{x}{d}) 。

通过插板法可以知道 g(x) = 2 ^ {x - 1} 。

感受:

容斥题,可以考虑莫比乌斯反演。

代码:

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const ll mod = 1e9 + 7 ;
ll qpow(ll a , ll b)
{
ll ans = 1 ;
a %= mod ;
while(b)
{
if(b & 1)
ans = (ans * a) % mod ;
b >>= 1 , a = (a * a) % mod ;
}
return ans % mod ;
}
ll get_mu(ll n)
{
ll x = n , temp = n ;
ll cnt = 0 , now = 0 ;
for(ll i = 2 ; i * i <= x ; i ++)
{
now = 0 ;
if(x % i == 0)
{
while(x % i == 0)
now ++ , x /= i ;
if(now > 1) return 0 ;
cnt ++ ;
}
}
if(x != 1) cnt ++ ;
return (cnt & 1) ? -1 : 1 ;
}
ll g(ll x)
{
return qpow(2ll , x - 1) ;
}
void solve(ll x)
{
ll ans = 0 ;
for(ll d = 1 ; d * d <= x ; d ++)
{
if(x % d != 0)
continue ;
ans += get_mu(d) * g(x / d) ;
if(d * d != x)
ans += get_mu(x / d) * g(d) ;
ans %= mod ;
}
ans = (ans + mod) % mod ;
printf("%lldn" , ans) ;
}
int main()
{
ll x , y ;
scanf("%lld%lld" , &x , &y) ;
if(y % x != 0){printf("0n") ; return 0 ;}
solve(y / x) ;
return 0 ;
}

 

最后

以上就是成就果汁为你收集整理的codeforces900D 2100分莫比乌斯反演题目传送门题意:题解:感受:代码:的全部内容,希望文章能够帮你解决codeforces900D 2100分莫比乌斯反演题目传送门题意:题解:感受:代码:所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(61)

评论列表共有 0 条评论

立即
投稿
返回
顶部