Codeforces Round #450 (Div. 2) D.Unusual Sequences (数学)

题目链接：

http://codeforces.com/contest/900/problem/D

题意：

给你 $x$ 和 $y$，让你求同时满足这两个条件的序列的个数：

$a_1, a_2, ..., a_n (1 ≤ a_i)$。

$ 1.$ $gcd(a_1, a_2, ..., a_n) = x $

$ 2.$ $\sum_{i=1}^{n}a_i = y$

题解：

可以发现，当$y\%x!=0$时，满足条件的序列不存在。让$f(t)$表示满足序列和为的 $t$，且$gcd$ 为 $1$ 的序列的个数。那么答案就是 $f(\frac{y}{x})$。

显然，用隔板法可以证明，把一个数 $x$ 分解成可以由几个数组成的序列有$2^{x-1}$个，假设$k=\frac{y}{x}$，把其中是质数的情况保留，把非质数的情况减去就可以了，这里用记忆化，容斥一下就可以得到答案了。

代码：

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;

#define ll long long

std::map<int, int> mp;

ll qpower(ll a,ll b,ll mod)

{

    ll ans = 1;

    while(b>0)

    {

        if(b&1) ans=(ans*a)%mod;

        b>>=1;

        a=(a*a)%mod;

    }

    return ans;

}

ll solve(int x)

{

  if(x==1)return 1;

  if (mp.count(x)) {

    return mp[x];

  }

  mp[x] = qpower(2,x-1,mod);

  for(int i=2;i*i<=x;i++) {

    if(x%i==0){

      mp[x] = (mp[x] - solve(x/i) + mod) % mod;

      if(i!=x/i){

        mp[x] = (mp[x] - solve(i) + mod) % mod;

      }

    }

  }

  mp[x] = (mp[x] - solve(1) + mod) % mod;

  return mp[x];

}

int x,y;

int main(int argc, char const *argv[]) {

  std::cin >> x >> y;

  if(y%x!=0){

    std::cout << "0" << '\n';

    return 0;

  }

  std::cout << solve(y/x) << '\n';

  return 0;

}

巴特西

Codeforces Round #450 (Div. 2) D.Unusual Sequences (数学)

题目链接：

http://codeforces.com/contest/900/problem/D

题意：

给你 \(x\) 和 \(y\)，让你求同时满足这两个条件的序列的个数：

\(a_1, a_2, ..., a_n (1 ≤ a_i)\)。

$ 1.$ $gcd(a_1, a_2, ..., a_n) = x $

$ 2.$ \(\sum_{i=1}^{n}a_i = y\)

题解：

可以发现，当\(y\%x!=0\)时，满足条件的序列不存在。让\(f(t)\)表示满足序列和为的 \(t\)，且\(gcd\) 为 \(1\) 的序列的个数。那么答案就是 \(f(\frac{y}{x})\)。

显然，用隔板法可以证明，把一个数 \(x\) 分解成可以由几个数组成的序列有\(2^{x-1}\)个，假设\(k=\frac{y}{x}\)，把其中是质数的情况保留，把非质数的情况减去就可以了，这里用记忆化，容斥一下就可以得到答案了。

代码：

最新文章

热门文章