2020 Petrozavodsk Winter Camp Day 5 A

发表于 2020-06-02 更新于 2020-07-21 分类于数论，整除与同余

Problem A. Bags of Candies

Statement

把 $A = {1,2,\dots,n}$ 分成尽可能多对，使得每一对的两个数都不互质，问 $n$ 减去配对次数的值。有 $z$ 组测试数据。

$1 \leq z \leq 5$

$2 \leq n \leq 10^{11}$

Solution

半场的时候动这个题的队伍只有个位数。可能大家都觉得有别的题可做，不像我这么菜别的都不会就来瞎猜结论了啊。于是结论就是，将 $1$ 和大于 $\lfloor \frac n2 \rfloor$ 的质数从 $A$ 里删掉，剩下的集合 $A’$ 一定是可以匹配满的，所以配对次数就是 $\frac {|A’|}2$。

~~赛中是瞎猜的，~~这里给一个简单证明。

将 $A’$ 的所有元素按最大质因子 $d$ 分组，那么每组都可以表示成 $A_d = {d,2d,\dots,\lfloor \frac nd \rfloor d}$ 的形式（注意并不一定 $|A_d|=\lfloor \frac nd \rfloor$，比如 $77 \notin A_7$），显然组内的数都是不互质的。

如果 $|A_d|$ 是偶数，直接令组内的数任意两两配对；如果 $|A_d|$ 是奇数，则除了 $2d$ 以外任意两两配对。所有组都作完以上匹配之后，剩下的数都是 $2$ 的倍数，所以也都不互质，也可以任意两两配对。注意到对于任意 $d$ 有 $|A_d| \geq 2$ 即不存在 $|A_d| = 1$，所以最后剩下的数显然至多只有一个。

至此，剩下的任务就是筛 $10^{11}$ 以内的质数个数。这东西听上去很不可做，又或者是某种奥妙重重的高级筛法，但 clp012345 说有一种叫作 Meissel-Lehmer 的神棍算法可以 $O(n^\frac 23)$ 求这个东西，于是我~~临时找了个板子复制粘贴~~交了两发过了（？）。赛后看官方题解居然是分段打表，太暴力了……

关于这个算法的更多内容可以看上面的链接。

Code

#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#define all(v) (v).begin(), (v).end()
#define unq(v) (v).erase(unique(all(v)), (v).end())
#define ii int, int
#define li int, int
#define ll2 ll, ll
#define vec vector
#define pii pair <int, int>
#define pli pair <ll, int>
#define pll2 pair <ll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MULTI int T; cin >> T; while(T--)
#define sqr(x) ((x) * (x))
#define test cerr << '!' << endl;
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main0 ();
int main () {
	#ifndef ONLINE_JUDGE
		freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
	#endif
	ios::sync_with_stdio(false);
	clock_t start, end;
	// start = clock();
	main0();
	// end = clock();
	// cout << (end - start) << endl;
	#ifndef ONLINE_JUDGE
		fclose(stdin);
	#endif
	return 0;
}
 
const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double Pi = acos(-1.0);
 
const int N = 5e6 + 2;//通过知道前面的n^1/3的=质数可以推断后面n^2/3的质数所以可以适当减小
bool np[N];
int prime[N], pi[N];
int getprime()
{
    int cnt = 0;
    np[0] = np[1] = true;
    pi[0] = pi[1] = 0;
    for(int i = 2; i < N; ++i)
    {
        if(!np[i]) prime[++cnt] = i;
        pi[i] = cnt;
        for(int j = 1; j <= cnt && i * prime[j] < N; ++j)
        {
            np[i * prime[j]] = true;
            if(i % prime[j] == 0)   break;
        }
    }
    return cnt;
}
const int M = 7;//为了减小内存可以不过是质数
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;//为了减小内存可以不过要按质数减小如去掉17
int phi[PM + 1][M + 1], sz[M + 1];
void init()
{
    getprime();
    sz[0] = 1;
    for(int i = 0; i <= PM; ++i)  phi[i][0] = i;
    for(int i = 1; i <= M; ++i)
    {
        sz[i] = prime[i] * sz[i - 1];
        for(int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
    }
}
int sqrt2(ll x)
{
    ll r = (ll)sqrt(x - 0.1);
    while(r * r <= x)   ++r;
    return int(r - 1);
}
int sqrt3(ll x)
{
    ll r = (ll)cbrt(x - 0.1);
    while(r * r * r <= x)   ++r;
    return int(r - 1);
}
ll getphi(ll x, int s)
{
    if(s == 0)  return x;
    if(s <= M)  return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
    if(x <= prime[s]*prime[s])   return pi[x] - s + 1;
    if(x <= prime[s]*prime[s]*prime[s] && x < N)
    {
        int s2x = pi[sqrt2(x)];
        ll ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
        for(int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]];
        return ans;
    }
    return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}
ll getpi(ll x)
{
    if(x < N)   return pi[x];
    ll ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
    for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1;
    return ans;
}
ll lehmer_pi(ll x)
{
    if(x < N)   return pi[x];
    int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
    int b = (int)lehmer_pi(sqrt2(x));
    int c = (int)lehmer_pi(sqrt3(x));
    ll sum = getphi(x, a) +(ll)(b + a - 2) * (b - a + 1) / 2;
    for (int i = a + 1; i <= b; i++)
    {
        ll w = x / prime[i];
        sum -= lehmer_pi(w);
        if (i > c) continue;
        ll lim = lehmer_pi(sqrt2(w));
        for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1);
    }
    return sum;
}
 
int main0 () {
	init();
	MULTI {
		ll n;
		cin >> n;
		//cout << lehmer_pi(n) << ' ' << lehmer_pi(n / 2) << endl;
		ll k = lehmer_pi(n) - lehmer_pi(n / 2) + 1;
		cout << n - (n - k) / 2 << endl;
	}
}