2022威海ccpc G 打表

题意：

给出$l,r$，计算
$$\sum _{i=l}^r[gcd((ix)xorx,x)=1]$$

Solution：

今天学了莫比乌斯反演来补这题，发现化的形式更难了，这么多人过的铜牌题，大家都是打表，直接打表$gcd((ix)xorx,x)$，存在一个长度$2^{\lceil lo{g}_{2}x\rceil }$的循环节，就可以直接计算了

比赛的时候发现有循环节了，不过打的是$(ix)xorx$的表。。还是差分数组的循环节

#include 
using namespace std;

using ll=long long;

ll x,n,len,sum[10000005];

ll solve(ll limit)
{
	ll ret=limit/len*sum[len],left=limit%len;
	return ret+sum[left];
}

int main()
{
	cin>>x>>n;
	for(int i=30;i>=0;i--)
	{
		if((1<<i)&x)
		{
			len=1ll<<(i+1);
			break;
		}
	}
	for(int i=1;i<=len;i++) sum[i]=sum[i-1]+(__gcd(i*x^x,x)==1);
	while(n--)
	{
		ll l,r; scanf("%lld%lld",&l,&r);
		printf("%lld\n",solve(r)-solve(l-1));
	}
	return 0;
}
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