# Codeforces215e periodical numbers

## 细节超多的数位DP

Posted by yjjr's blog on March 13, 2019

# Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=106;
int a[maxn];ll f[maxn],n,m;
inline ll cal(int len,int j,ll x){
ll c=0,b=1;
rep(i,1,j)c+=(a[len-i+1]<<(j-i));
b=c;
rep(i,1,len/j-1)b<<=j,b+=c;
return (ll)(c-(ll)(1<<(j-1))+(b<=x));
}

inline ll solve(ll x){
int len=0;ll tmp=x,ans=0;
while(tmp){
a[++len]=tmp&1;
tmp>>=1;
}
rep(i,2,len){
mem(f,0);
rep(j,1,i/2){
if(i%j!=0)continue;
if(i<len)f[j]+=(1<<(j-1));else f[j]+=cal(len,j,x);
rep(k,1,j-1)if(j%k==0)f[j]-=f[k];
ans+=f[j];
}
}
return ans;
}
int main(){