@[KSCD_](/user/544549) 代码
by __Tonycyt__ @ 2024-03-06 21:03:18
@[__Tonycyt__](/user/667037)
```cpp
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cstring>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e6+10;
const int M=1e5+10;
const int K=64+10;
const int mod=1e6+3;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
return s*w;
}
int po[K],sum[K];
void mk()
{
po[0]=1,sum[0]=1;
for(int i=1;i<=60;i++) po[i]=po[i-1]*2,sum[i]=sum[i-1]*3%mod;
}
int s(int x)
{
if(x%2==0) return x/2%mod*(x%mod+1)%mod;
else return (x+1)/2%mod*x%mod;
}
int f(int x)
{
if(x==0) return 0;
int l=0,r=60,p;
while(l<=r)
{
int mid=(l+r)/2;
if(po[mid]<=x) p=mid,l=mid+1;
else r=mid-1;
}
if(po[p]==x) return sum[p];
else return (sum[p]+2*(f(x%po[p]))%mod)%mod;
}
signed main()
{
mk();
int n=read();
cout<<(s(n)-f(n)+mod)%mod;
return 0;
}
```
我觉得在记录里有就没发来着
by KSCD_ @ 2024-03-06 21:04:33
死因：中间乘法会爆longlong，开__int128后过了
本帖完结。
by KSCD_ @ 2024-03-06 21:27:01