周周练4

B、Rinne Loves Xor

大概就是一个数字分别异或一些数字的结果的和等于一个数字异或这些数字的和

然后就跑一下前缀和，遍历一遍就做完了

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll a[100005][32];
ll b[100005][32];
const ll mod = 1e9 + 7;
int main()
{
	int n;
	sc("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		ll t;
		sc("%lld", &t);
		for (int j = 0; j < 32; j++)
		{
			if (t & (1LL << j))
				a[i][j] = 1;
			a[i][j] += a[i - 1][j];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		ll t;
		sc("%lld", &t);
		for (int j = 0; j < 32; j++)
		{
			if (t & (1LL << j))
				b[i][j] = 1;
			b[i][j] += b[i - 1][j];
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 32; j++)
		{
			if (a[i][j] - a[i - 1][j] != b[i][j] - b[i - 1][j])
				ans = (ans + (1LL << j)) % mod;
			if (a[i][j] - a[i - 1][j] == 1)
				ans = (ans + (1LL << j) * (i - 1 - b[i - 1][j])) % mod;
			else
				ans = (ans + (1LL << j) * b[i - 1][j]) % mod;
			if (b[i][j] - b[i - 1][j] == 1)
				ans = (ans + (1LL << j) * (i - 1 - a[i - 1][j])) % mod;
			else
				ans = (ans + (1LL << j) * a[i - 1][j]) % mod;
		}
		pr("%lld%c", ans, i == n ? '\n' : ' ');
	}
}

C、阶乘

求一个最小的正整数 n，使得 n! 是 p 的倍数

考虑若 n 成立，那么所有>=n的数字的阶乘均成立，具有单调性，所以我们先枚举因子，然后二分出 n 即可，最后取一个最大值就是答案，主要 n 自己可能是个质数，所以最后和 n 取个最大值

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
bool check(ll k, ll num, ll all)
{
	ll ans = 0;
	for (int i = num; i <= k * num; i = i * num)
	{
		ans += k * num / i;
		if (ans > 50)
			return true;
	}
	if (ans >= all)
		return true;
	return false;
}
ll get(ll n)
{
	ll ans = 1;
	for (ll i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			ll cnt = 0;
			while (n % i == 0)
			{
				n /= i;
				cnt++;
			}
			ll l = 1, r = 1e9;
			while (l + 1 < r)
			{
				ll k = (l + r) / 2;
				if (check(k, i, cnt))
					r = k;
				else
					l = k;
			}
			if (!check(l, i, cnt))
				l = r;
			ans = max(ans, i * l);
		}
	}
	if (n > 1)
	{
		ans = max(ans, n);
	}
	return ans;
}
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		ll n;
		sc("%lld", &n);
		pr("%lld\n", get(n));
	}
}

D、小石的签到题

考虑 1 可以单独取一手，也可以被其他任意一手取掉，如果第一个人先手不取 1 会输的话，那么他会先取1，反之，不取1，就是说第一个人稳赢，然后特判一下 n=1的情况

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    if (n == 1)
        printf("Yang");
    else
        printf("Shi");
}

E、装备合成

有 n 个 a 和 m 个 b，2个a和3个b合成一件

装备，4个a和1个b合成一件装备，求最大合成的装备数量

首先假设合成了x个装备1和y个装备2

2x+3y<=n

3x+y<=m

z=x+y

然后会发现这玩意儿是个二次函数，先增再减，所以三分一下即可，由于精度存在问题，所以装备个数取double去比较，然后比较一下它左右两边的值即可

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
double a, b;
double calc(ll numa)
{
    double aa = a, bb = b;
    aa -= numa * 2;
    bb -= numa * 3;
    double ans = numa + min(aa / 4, bb);
    return ans;
}
int main()
{
    int T;
    sc("%d", &T);
    while (T--)
    {
        sc("%lf%lf", &a, &b);
        ll l = 0, r = min(a / 2, b / 3);//numa
        while (l + 2 < r)
        {
            ll lmid = (r - l) / 3 + l;
            ll rmid = (r - l) / 3 * 2 + l;
            double lans = calc(lmid);
            double rans = calc(rmid);
            if (lans < rans)
                l = lmid;
            else
                r = rmid;
        }
        ll ans = 0;
        for (ll i = l; i <= r; i++)
            ans = max(ans, (ll)calc(i));
        pr("%lld\n", ans);
    }
}