QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#48068	#4634. Factor	Yudanjun	AC ✓	1034ms	24472kb	C++20	793b	2022-09-11 15:03:36	2022-09-11 15:03:37

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-09-11 15:03:37]
Judged

Verdict: AC
Time: 1034ms
Memory: 24472kb

Show

[2022-09-11 15:03:36]
Submitted

answer

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define N 2100005
using namespace std;
int n,tot,ans;
int f[N],pri[N];
bitset<N> p;
void init(int M){
	for(int i=2;i<=M;i++){
		if(!p[i]) pri[++tot]=i;
		for(int j=1;j<=tot&&i*pri[j]<=M;j++){
			p[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
	for(int i=2;i<=M;i++) f[i]=p[i]?f[i-1]:f[i-1]+1;
} 
void solve(int x,int val,int mul){
	ans++;
	for(int i=x+1;i<=tot&&val*pri[i]<=n&&mul>=pri[i]-1;i++){
		if(val*pri[i]*pri[i]>n){
			ans+=f[min(mul+1,n/val)]-i+1;
			break;
		}
		int nval=val,pw=1,sum=1;
		while(nval*pri[i]<=n){
			nval*=pri[i];pw*=pri[i];sum+=pw;
			solve(i,nval,mul*sum);
		}
	}
}
signed main(){
	cin>>n;
	init(2100000);
	solve(0,1,1);
	cout<<ans<<endl;
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 29ms

memory: 22236kb

input:

output:

result:

ok single line: '5'

Test #2:

score: 0

Accepted

time: 28ms

memory: 24292kb

input:

output:

result:

ok single line: '9'

Test #3:

score: 0

Accepted

time: 26ms

memory: 24288kb

input:

output:

result:

ok single line: '17'

Test #4:

score: 0

Accepted

time: 29ms

memory: 24472kb

input:

output:

result:

ok single line: '4'

Test #5:

score: 0

Accepted

time: 29ms

memory: 22272kb

input:

output:

result:

ok single line: '26'

Test #6:

score: 0

Accepted

time: 20ms

memory: 22244kb

input:

output:

result:

ok single line: '130'

Test #7:

score: 0

Accepted

time: 27ms

memory: 22172kb

input:

output:

result:

ok single line: '806'

Test #8:

score: 0

Accepted

time: 29ms

memory: 24204kb

input:

output:

result:

ok single line: '10905'

Test #9:

score: 0

Accepted

time: 24ms

memory: 21852kb

input:

output:

result:

ok single line: '95960'

Test #10:

score: 0

Accepted

time: 24ms

memory: 24304kb

input:

output:

result:

ok single line: '494209'

Test #11:

score: 0

Accepted

time: 25ms

memory: 22260kb

input:

51133311

output:

result:

ok single line: '3851066'

Test #12:

score: 0

Accepted

time: 32ms

memory: 24304kb

input:

607519174

output:

40319008

result:

ok single line: '40319008'

Test #13:

score: 0

Accepted

time: 56ms

memory: 24468kb

input:

7739876803

output:

456270136

result:

ok single line: '456270136'

Test #14:

score: 0

Accepted

time: 182ms

memory: 22116kb

input:

80754680817

output:

4304423738

result:

ok single line: '4304423738'

Test #15:

score: 0

Accepted

time: 1034ms

memory: 24324kb

input:

1000000000000

output:

48366248808

result:

ok single line: '48366248808'

Test #16:

score: 0

Accepted

time: 484ms

memory: 24304kb

input:

300000000000

output:

15176932897

result:

ok single line: '15176932897'

Test #17:

score: 0

Accepted

time: 629ms

memory: 24404kb

input:

500000000000

output:

24808936807

result:

ok single line: '24808936807'

Test #18:

score: 0

Accepted

time: 797ms

memory: 22048kb

input:

700000000000

output:

34300642547

result:

ok single line: '34300642547'

Test #19:

score: 0

Accepted

time: 879ms

memory: 24468kb

input:

790673894439

output:

38570752521

result:

ok single line: '38570752521'