brz的杯子

思维题

题目分析：x|y表示x整除y，也就是说x是y的因子，题目大意就是给你n个杯子，m个数（每个数都是无限多个的）你要填充满全部的杯子，因为1是任何比它大的数的因子，那么我们把第一个位置放1，后序所有素数的位置放2，因为题目说了保证下标如果y是x的因子，那么第x个杯子所放的数字一定大于第y个杯子的数，我们可以打表来看

位置：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
数字：1,2,2,3,2,3,2,4,3, 3, 2, 4, 2, 3, 3, 5

这样就一目了然了，观察1,2,4,8,16我们可以发现规律，发现每到下标为2的幂的位置，所需要的最大数都会加1，我们用二进制的思想来看，可以发现最大数其实就是二进制的位数。

AC代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <queue>
#include <string.h>
typedef long long ll;
using namespace std;
#define pi acos(-1.0)
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int solve(int x)
{
    int ans = 0;
    while (x)
    {
        x >>= 1;
        ans++;
    }
    return ans;
}
int main()
{
    int t, ans = 0;
    scanf("%d", &t);
    for (int i = 1; i <= t; ++i)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        if (m >= solve(n))
            ans ^= i;
        else
            ans ^= i - 1;
    }
    printf("%d\n", ans);
}