QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#792063 | #9270. Deep Primes | bulijiojiodibuliduo# | AC ✓ | 2ms | 8500kb | C++17 | 4.6kb | 2024-11-28 23:17:52 | 2024-11-28 23:17:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
typedef pair<ll,ll> PLL;
namespace Factor {
const int DEFAULT_SZ=100000;
bool ISINIT=false;
const int N=1010000;
ll C,fac[10010],n,mut,a[1001000];
int T,cnt,i,l,prime[N],p[N],psize,_cnt;
ll _e[100],_pr[100];
vector<ll> d;
inline ll mul(ll a,ll b,ll p) {
if (p<=1000000000) return a*b%p;
else if (p<=1000000000000ll) return (((a*(b>>20)%p)<<20)+(a*(b&((1<<20)-1))))%p;
else {
ll d=(ll)floor(a*(long double)b/p+0.5);
ll ret=(a*b-d*p)%p;
if (ret<0) ret+=p;
return ret;
}
}
void prime_table(){
int i,j,tot,t1;
for (i=1;i<=psize;i++) p[i]=i;
for (i=2,tot=0;i<=psize;i++){
if (p[i]==i) prime[++tot]=i;
for (j=1;j<=tot && (t1=prime[j]*i)<=psize;j++){
p[t1]=prime[j];
if (i%prime[j]==0) break;
}
}
}
void init(int ps) {
psize=ps;
prime_table();
ISINIT=true;
}
ll powl(ll a,ll n,ll p) {
ll ans=1;
for (;n;n>>=1) {
if (n&1) ans=mul(ans,a,p);
a=mul(a,a,p);
}
return ans;
}
bool witness(ll a,ll n) {
int t=0;
ll u=n-1;
for (;~u&1;u>>=1) t++;
ll x=powl(a,u,n),_x=0;
for (;t;t--) {
_x=mul(x,x,n);
if (_x==1 && x!=1 && x!=n-1) return 1;
x=_x;
}
return _x!=1;
}
bool miller(ll n) {
if (!ISINIT) init(DEFAULT_SZ);
if (n<2) return 0;
if (n<=psize) return p[n]==n;
if (~n&1) return 0;
for (int j=0;j<=7;j++) if (witness(rand()%(n-1)+1,n)) return 0;
return 1;
}
ll gcd(ll a,ll b) {
ll ret=1;
while (a!=0) {
if ((~a&1) && (~b&1)) ret<<=1,a>>=1,b>>=1;
else if (~a&1) a>>=1; else if (~b&1) b>>=1;
else {
if (a<b) swap(a,b);
a-=b;
}
}
return ret*b;
}
ll rho(ll n) {
for (;;) {
ll X=rand()%n,Y,Z,T=1,*lY=a,*lX=lY;
int tmp=20;
C=rand()%10+3;
X=mul(X,X,n)+C;*(lY++)=X;lX++;
Y=mul(X,X,n)+C;*(lY++)=Y;
for(;X!=Y;) {
ll t=X-Y+n;
Z=mul(T,t,n);
if(Z==0) return gcd(T,n);
tmp--;
if (tmp==0) {
tmp=20;
Z=gcd(Z,n);
if (Z!=1 && Z!=n) return Z;
}
T=Z;
Y=*(lY++)=mul(Y,Y,n)+C;
Y=*(lY++)=mul(Y,Y,n)+C;
X=*(lX++);
}
}
}
void _factor(ll n) {
if (!ISINIT) init(DEFAULT_SZ);
for (int i=0;i<cnt;i++) {
if (n%fac[i]==0) n/=fac[i],fac[cnt++]=fac[i];}
if (n<=psize) {
for (;n!=1;n/=p[n]) fac[cnt++]=p[n];
return;
}
if (miller(n)) fac[cnt++]=n;
else {
ll x=rho(n);
_factor(x);_factor(n/x);
}
}
void dfs(ll x,int dep) {
if (dep==_cnt) d.pb(x);
else {
dfs(x,dep+1);
for (int i=1;i<=_e[dep];i++) dfs(x*=_pr[dep],dep+1);
}
}
void norm() {
sort(fac,fac+cnt);
_cnt=0;
rep(i,0,cnt) if (i==0||fac[i]!=fac[i-1]) _pr[_cnt]=fac[i],_e[_cnt++]=1;
else _e[_cnt-1]++;
}
vector<ll> getd() {
d.clear();
dfs(1,0);
return d;
}
vector<ll> factor(ll n) {
cnt=0;
_factor(n);
norm();
return getd();
}
vector<PLL> factorG(ll n) {
cnt=0;
_factor(n);
norm();
vector<PLL> d;
rep(i,0,_cnt) d.pb(mp(_pr[i],_e[i]));
return d;
}
bool is_primitive(ll a,ll p) {
assert(miller(p));
vector<PLL> D=factorG(p-1);
a%=p;
if (a<0) a+=p;
if (a==0) return 0;
rep(i,0,SZ(D)) if (powl(a,(p-1)/D[i].fi,p)==1) return 0;
return 1;
}
ll get_primitive(ll p) {
assert(miller(p));
vector<PLL> D=factorG(p-1);
for (int a=1;a<p;a++) {
bool val=1;
rep(i,0,SZ(D)) if (powl(a,(p-1)/D[i].fi,p)==1) {
val=0;
break;
}
if (val) return a;
}
return -1;
}
}
ll l,r;
bool check(ll x) {
string o=to_string(x);
rep(i,0,SZ(o)) rep(j,i,SZ(o)) {
string op=o.substr(i,j-i+1);
ll y=stol(op);
if (!Factor::miller(y)) return false;
}
return true;
}
vector<ll> ret;
int ans;
void dfs(ll x) {
if (!check(x)) return;
ret.pb(x);
//printf("%lld\n",x);
dfs(x*10+3);
dfs(x*10+7);
}
int main() {
dfs(2);
dfs(3);
dfs(5);
dfs(7);
scanf("%lld%lld",&l,&r);
for (auto x:ret) if (x>=l&&x<=r) ans+=1;
printf("%d\n",ans);
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 8248kb
input:
1 11
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 8280kb
input:
1 1
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 2ms
memory: 6340kb
input:
1 1000000000000000000
output:
9
result:
ok answer is '9'
Test #4:
score: 0
Accepted
time: 0ms
memory: 6232kb
input:
1000000000000000000 1000000000000000000
output:
0
result:
ok answer is '0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 6244kb
input:
736 738
output:
0
result:
ok answer is '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 6336kb
input:
5373 5374
output:
0
result:
ok answer is '0'
Test #7:
score: 0
Accepted
time: 2ms
memory: 8192kb
input:
1 3
output:
2
result:
ok answer is '2'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7988kb
input:
2 9
output:
4
result:
ok answer is '4'
Test #9:
score: 0
Accepted
time: 2ms
memory: 8212kb
input:
2 4
output:
2
result:
ok answer is '2'
Test #10:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
3 373
output:
8
result:
ok answer is '8'
Test #11:
score: 0
Accepted
time: 1ms
memory: 6272kb
input:
4 6
output:
1
result:
ok answer is '1'
Test #12:
score: 0
Accepted
time: 1ms
memory: 6324kb
input:
5 55
output:
5
result:
ok answer is '5'
Test #13:
score: 0
Accepted
time: 1ms
memory: 6336kb
input:
6 8
output:
1
result:
ok answer is '1'
Test #14:
score: 0
Accepted
time: 2ms
memory: 8448kb
input:
7 39
output:
3
result:
ok answer is '3'
Test #15:
score: 0
Accepted
time: 1ms
memory: 6312kb
input:
22 24
output:
1
result:
ok answer is '1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 6256kb
input:
23 40
output:
2
result:
ok answer is '2'
Test #17:
score: 0
Accepted
time: 0ms
memory: 6204kb
input:
36 38
output:
1
result:
ok answer is '1'
Test #18:
score: 0
Accepted
time: 1ms
memory: 6232kb
input:
37 53
output:
2
result:
ok answer is '2'
Test #19:
score: 0
Accepted
time: 2ms
memory: 8500kb
input:
52 54
output:
1
result:
ok answer is '1'
Test #20:
score: 0
Accepted
time: 0ms
memory: 8068kb
input:
53 378
output:
3
result:
ok answer is '3'
Test #21:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
72 74
output:
1
result:
ok answer is '1'
Test #22:
score: 0
Accepted
time: 2ms
memory: 8144kb
input:
73 374
output:
2
result:
ok answer is '2'
Test #23:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
372 374
output:
1
result:
ok answer is '1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 6264kb
input:
645762258982631932 885295149831742591
output:
0
result:
ok answer is '0'
Test #25:
score: 0
Accepted
time: 0ms
memory: 6548kb
input:
819875141880895728 946247261349950347
output:
0
result:
ok answer is '0'
Test #26:
score: 0
Accepted
time: 0ms
memory: 8444kb
input:
891351282707723857 891429887621456547
output:
0
result:
ok answer is '0'
Test #27:
score: 0
Accepted
time: 1ms
memory: 6288kb
input:
520974001910286918 960365366546346049
output:
0
result:
ok answer is '0'
Test #28:
score: 0
Accepted
time: 1ms
memory: 6556kb
input:
856674611404539679 912190643721143050
output:
0
result:
ok answer is '0'
Test #29:
score: 0
Accepted
time: 2ms
memory: 8076kb
input:
711066337317063340 908820864712129941
output:
0
result:
ok answer is '0'
Test #30:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
234122432773361868 906278314445745617
output:
0
result:
ok answer is '0'
Test #31:
score: 0
Accepted
time: 2ms
memory: 8008kb
input:
999594448650287940 999671970710526657
output:
0
result:
ok answer is '0'
Test #32:
score: 0
Accepted
time: 0ms
memory: 6260kb
input:
676105575462224593 841790036199317881
output:
0
result:
ok answer is '0'
Test #33:
score: 0
Accepted
time: 0ms
memory: 6344kb
input:
752304352384836991 848405248582489040
output:
0
result:
ok answer is '0'
Test #34:
score: 0
Accepted
time: 0ms
memory: 6260kb
input:
291499943576823355 462093425359000422
output:
0
result:
ok answer is '0'
Test #35:
score: 0
Accepted
time: 1ms
memory: 6236kb
input:
192583020404011431 945814124262134310
output:
0
result:
ok answer is '0'
Test #36:
score: 0
Accepted
time: 1ms
memory: 6556kb
input:
363434583954291757 947385169886199754
output:
0
result:
ok answer is '0'
Test #37:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
594688604155374934 649541852103467921
output:
0
result:
ok answer is '0'
Test #38:
score: 0
Accepted
time: 1ms
memory: 6516kb
input:
662180230164163676 899422968245266530
output:
0
result:
ok answer is '0'
Test #39:
score: 0
Accepted
time: 1ms
memory: 6556kb
input:
543390476138996221 576565748335876400
output:
0
result:
ok answer is '0'
Test #40:
score: 0
Accepted
time: 1ms
memory: 6268kb
input:
746055710353195922 859032117962645886
output:
0
result:
ok answer is '0'
Test #41:
score: 0
Accepted
time: 1ms
memory: 6272kb
input:
935387048910748511 999143227013178277
output:
0
result:
ok answer is '0'
Test #42:
score: 0
Accepted
time: 2ms
memory: 8072kb
input:
617116466913575467 892257825396149858
output:
0
result:
ok answer is '0'
Extra Test:
score: 0
Extra Test Passed