QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#48064	#4634. Factor	Yudanjun	AC ✓	1079ms	24472kb	C++20	829b	2022-09-11 14:54:03	2022-09-11 14:54:06

Judging History

你现在查看的是最新测评结果

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

[2022-09-11 14:54:06]
评测

测评结果：AC
用时：1079ms
内存：24472kb

查看

[2022-09-11 14:54:03]
提交

answer

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
#define N 2100005
using namespace std;
int n,tot,ans,mx;
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){
			mx=max(mx,min(mul+1,n/val));
			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: 31ms

memory: 24292kb

input:

output:

result:

ok single line: '5'

Test #2:

score: 0

Accepted

time: 28ms

memory: 24404kb

input:

output:

result:

ok single line: '9'

Test #3:

score: 0

Accepted

time: 34ms

memory: 22068kb

input:

output:

result:

ok single line: '17'

Test #4:

score: 0

Accepted

time: 32ms

memory: 24328kb

input:

output:

result:

ok single line: '4'

Test #5:

score: 0

Accepted

time: 22ms

memory: 22372kb

input:

output:

result:

ok single line: '26'

Test #6:

score: 0

Accepted

time: 25ms

memory: 24400kb

input:

output:

result:

ok single line: '130'

Test #7:

score: 0

Accepted

time: 30ms

memory: 24260kb

input:

output:

result:

ok single line: '806'

Test #8:

score: 0

Accepted

time: 25ms

memory: 22108kb

input:

output:

result:

ok single line: '10905'

Test #9:

score: 0

Accepted

time: 32ms

memory: 24324kb

input:

output:

result:

ok single line: '95960'

Test #10:

score: 0

Accepted

time: 23ms

memory: 24404kb

input:

output:

result:

ok single line: '494209'

Test #11:

score: 0

Accepted

time: 32ms

memory: 24472kb

input:

51133311

output:

result:

ok single line: '3851066'

Test #12:

score: 0

Accepted

time: 30ms

memory: 24328kb

input:

607519174

output:

40319008

result:

ok single line: '40319008'

Test #13:

score: 0

Accepted

time: 58ms

memory: 24388kb

input:

7739876803

output:

456270136

result:

ok single line: '456270136'

Test #14:

score: 0

Accepted

time: 196ms

memory: 24332kb

input:

80754680817

output:

4304423738

result:

ok single line: '4304423738'

Test #15:

score: 0

Accepted

time: 1079ms

memory: 24420kb

input:

1000000000000

output:

48366248808

result:

ok single line: '48366248808'

Test #16:

score: 0

Accepted

time: 453ms

memory: 24332kb

input:

300000000000

output:

15176932897

result:

ok single line: '15176932897'

Test #17:

score: 0

Accepted

time: 646ms

memory: 22184kb

input:

500000000000

output:

24808936807

result:

ok single line: '24808936807'

Test #18:

score: 0

Accepted

time: 950ms

memory: 24332kb

input:

700000000000

output:

34300642547

result:

ok single line: '34300642547'

Test #19:

score: 0

Accepted

time: 888ms

memory: 24268kb

input:

790673894439

output:

38570752521

result:

ok single line: '38570752521'