Educational Codeforces Round 138 (Rated for Div. 2)

数论 + 计数

Problem - D - Codeforces

题意

给定整数 \(n\;(1<=n<=3e5),\;m\;(1<=m<=1e12)\)

要求求长度为 \(n\) 的数组，满足下列条件的个数

\(1<=a[i]<=m\)
对于每个位置 \(i\), 当 \(\gcd(a[i],i)=1\) 时可删去这个元素，直到删完所有元素；这个删除的过程是唯一的（即每次删除都有且只有一个位置可以删）（某个元素被删除后，他后面的元素会补上来，下标都 - 1）

思路

因为 \(\gcd(a[1],1)=1\) 恒成立，所有每次删除都可以删第一个元素，要删除的过程是唯一的，则需要每次删除时只有第一个位置可以被删
对于第 \(i\) 个位置，因为每次都会删第一个元素，所以 \(y=a[i]\) 这个值会依次出现在 \(i,i-1,i-2...2,1\) 这些位置上，并且只有在位置1 可以被删除，所以 \(a[i]\) 要与 \(1,2,3...,i\) 均不互质，即是 \([1,i]\) 中的所有质数的倍数
维护 \([1,i]\) 的质数积 \(tmp\) 即可，第 \(i\) 个位置可以取的数就是 \(\lfloor \frac m{tmp}\rfloor\); 注意 \(tmp>m\) 时就没必要再更新了，防止溢出
注意 \(m<=1e12\), 在计算答案时 \(m\) 需要先取模再计算！！！

代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 3e5 + 10;

const int mod = 998244353;

ll n, m;

int pr[N / 5], p[N], cnt;

ll f[N], s[N];

void get_primes(int n)

{

	p[1] = 1;

	for (int i = 2; i <= n; i++)

	{

		if (!p[i])

		{

			p[i] = i;

			pr[++cnt] = i;

		}

		for (int j = 1; j <= cnt && pr[j] <= n / i; j++)

		{

			p[i * pr[j]] = pr[j];

			if (p[i] == pr[j])

				break;

		}

	}

}

ll qmi(ll a, ll b)

{

	ll ans = 1;

	while(b)

	{

		if (b & 1)

			ans = ans * a % mod;

		b >>= 1;

		a = a * a % mod;

	}

	return ans;

}

int main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	get_primes(N - 10);

	cin >> n >> m;

	ll sub = 0;

	ll tmp = 1;

	s[0] = 1;

	for (int i = 1; i <= n; i++)

	{

		if (p[i] == i && tmp <= m)

			tmp *= i;

		f[i] = m / tmp % mod;

		s[i] = s[i-1] * f[i] % mod;

		sub = (sub + s[i]) % mod;

	}

	ll ans = 0;

	for (int i = 1; i <= n; i++)

		ans = (ans + qmi(m % mod, i)) % mod;

	ans = (ans - sub + mod) % mod;

	cout << ans << endl;

    return 0;

}

巴特西

Educational Codeforces Round 138 (Rated for Div. 2) - D. Counting Arrays

数论 + 计数

题意

思路

代码

最新文章

热门文章