TopCoderOpen 2020 Round1B : Hard EllysDifferentPrimes

今回も出なくてよかったな…。
(URL未確定)

問題

整数Nに近い素数のうち、全桁の数字が異なるものはどれか。

解法

Nは5*10^7以下なので、5.1*10^7以下の素数を列挙して総当たりしても間に合う。

bool ng[60000001];

class EllysDifferentPrimes {
	public:
	int getClosest(int N) {
		ZERO(ng);
		int i;
		vector<int> P;
		int ret=-1<<28;
		for(i=2;i<=51000000;i++) if(ng[i]==0) {
			for(int j=min(51000000LL,1LL*i*i);j<=51000000;j+=i) ng[j]=1;
			int mask=0;
			int j=i;
			while(j) {
				if(mask&(1<<(j%10))) break;
				mask |= (1<<(j%10));
				j/=10;
			}
			if(j==0 && abs(N-i)<abs(N-ret)) ret=i;
		}
		return ret;
		
		
	}
}

まとめ

これでレート増減したくはないな…。