CF900D 【Unusual Sequences】

数论好题

可以发现如果$x$不整除$y$那么肯定无解

不然我们可以发现其实求的就是和为$y/x$且$gcd(a_1,a_2,\cdots,a_n)=1$的序列个数

容易发现所有和为$y$的序列个数为$2^{n-1}$

而所有$gcd$不为$1$的序列,把每个数除以$gcd$,就又回到原题了

所以枚举每个可能的$gcd$(约数),递归计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define ll long long
const ll mod = 1e9 + 7;
std::map<int, int> m;
std::vector<int> v, vec;
int fast_pow(ll a, ll n)
{
int ret = 1;
while (n)
{
if (n & 1)
ret = (1ll * ret * a) % mod;
a = (1ll * a * a) % mod;
n >>= 1;
}
return ret;
}
int solve(int x)
{
if (m[x])
return m[x];
if (x == 1)
{
m[x] = 1;
return x;
}
int sum = 0;
int s = sqrt(x);
for (int i = 1; i <= s; i++)
{
if (x % i == 0)
{
if (i == 1 || i * i == x)
sum = (sum + solve(i)) % mod;
else
sum = (sum + solve(i) % mod + solve(x / i) % mod) % mod;
}
}
sum = (fast_pow(2, x - 1) - sum + mod) % mod;
m[x] = sum;
return sum;
}
int main()
{
ll x, y;
std::cin >> x >> y;
if (y % x != 0)
return 0 * printf("0");
y /= x;
std::cout << solve(y);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×