map记录数字拆解后的情况
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
using namespace std;
map<int,int> mp[2];
int n,ans=0;
inline void spl(int x,int op)
{
int k=x;
mp[op].clear();
while(k>0)//因为数字只有9位，不用搞什么特判去跳出
{
if(!mp[op][k%10])
{
mp[op][k%10]++;
if(op&&mp[0][k%10])
{
ans++;
return;
}
}
k/=10;
}
}
int main()
{
cin>>n;
spl(n,0);
int t = sqrt(n);
repd(i,1,t)
{
if(n%i==0)
{
if(i*i==n)
spl(t,1);
else
spl(i,1),spl(n/i,1);
}
}
cout<<ans;
return 0;
}
线性筛+二分，特判1
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define lowbit(x) (x&-x)
using namespace std;
const int N = 1E5+10,PN = N/2;
vector<int> prime;
int nprime[N];
void Euler()
{
for(int i=2;i<=N;i++)
{
if(!nprime[i])
nprime[i]=i,prime.push_back(i);
rep(j,0,prime.size())
{
if(prime[j]*i>N||prime[j]>nprime[i])
break;
else
nprime[i*prime[j]]=prime[j];
}
}
}
int ask(int x)
{
int pos=upper_bound(prime.begin(),prime.end(),x)-prime.begin();
return prime[pos]-prime[pos-1]-1;
}
int main()
{
Euler();
int t,x;
cin>>t;
repd(i,1,t)
{
cin>>x;
if(x==1||nprime[x]==x) cout<<0<<endl;
else cout<<ask(x)<<endl;
}
return 0;
}