难度超标 属实逆天
考完全员爆蛋(((
T1 ACM_51nod 1984
简要题意 定义 \(f_i\) 表示 \(\in x|i\) 的异或和
给定 \(n\) 求 \(1\to n\) 所有 \(f_i\) 的异或和
\(n\leq 10^{14}\)
很容易想到枚举每个约数 然后算出现次数异或
时间复杂度 \(O(n)\)
过不去 发现可以用整除分块优化 时间复杂度降成 \(O(\sqrt n)\)
现在的问题转化为怎么快速求出 \(1\to x\) 的异或和
发现有规律 找规律 \(O(1)\) 即可求得
#include<bits/stdc++.h>
#define ll long long
#define reg register
using namespace std;
ll n,ans;
inline ll get(ll x)
{
if(x%4==0) return x;
if(x%4==1) return 1;
if(x%4==2) return x+1;
return 0;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%lld",&n);
for(ll l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
if((n/l)&1) ans^=get(r)^get(l-1);
}
printf("%lld",ans);
return 0;
}
T2 亿只只因的回家路
咕了先(((
T3 西琳的魔法字符串
咕了 非常逆天的一道题目 思维和代码量都不小