QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#48028	#4634. Factor	Pure_Furies	AC ✓	1107ms	95484kb	C++	683b	2022-09-11 10:36:34	2022-09-11 10:36:35

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 10:36:35]
评测

测评结果：AC
用时：1107ms
内存：95484kb

查看

[2022-09-11 10:36:34]
提交

answer

#include<bits/stdc++.h>
using namespace std;
long long n,ans;
bool ispr[50000003];
int pr[1000003],m;
int sum[50000003];
void solve(int i,long long nw,long long mul){
	ans++;
	for(int j=i+1;pr[j]-1<=mul&&nw*pr[j]<=n;j++){
		if(nw*pr[j]*pr[j]>n){
			ans+=sum[min(n/nw,mul+1)]-j+1;
			break;
		}
		long long _nw=nw,pw=1,sum=1;
		while(_nw*pr[j]<=n){
			pw*=pr[j];
			sum+=pw;
			_nw*=pr[j];
			solve(j,_nw,mul*sum);
		}
	}
}
int main(){
	cin>>n;
	memset(ispr,1,sizeof(ispr));
	for(int i=2;i<=10000000;i++){
		if(ispr[i]){
			sum[i]=1;
			pr[++m]=i;
			for(int j=i;j<=10000000;j+=i)
				ispr[j]=0;
		}
		sum[i]+=sum[i-1];
	}solve(0,1,1);
	cout<<ans;
}

Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 103ms

memory: 95272kb

input:

output:

result:

ok single line: '5'

Test #2:

score: 0

Accepted

time: 91ms

memory: 95076kb

input:

output:

result:

ok single line: '9'

Test #3:

score: 0

Accepted

time: 89ms

memory: 95352kb

input:

output:

result:

ok single line: '17'

Test #4:

score: 0

Accepted

time: 88ms

memory: 95428kb

input:

output:

result:

ok single line: '4'

Test #5:

score: 0

Accepted

time: 89ms

memory: 94752kb

input:

output:

result:

ok single line: '26'

Test #6:

score: 0

Accepted

time: 92ms

memory: 94048kb

input:

output:

result:

ok single line: '130'

Test #7:

score: 0

Accepted

time: 94ms

memory: 94672kb

input:

output:

result:

ok single line: '806'

Test #8:

score: 0

Accepted

time: 85ms

memory: 94892kb

input:

output:

result:

ok single line: '10905'

Test #9:

score: 0

Accepted

time: 87ms

memory: 95308kb

input:

output:

result:

ok single line: '95960'

Test #10:

score: 0

Accepted

time: 80ms

memory: 94928kb

input:

output:

result:

ok single line: '494209'

Test #11:

score: 0

Accepted

time: 83ms

memory: 94116kb

input:

51133311

output:

result:

ok single line: '3851066'

Test #12:

score: 0

Accepted

time: 83ms

memory: 95316kb

input:

607519174

output:

40319008

result:

ok single line: '40319008'

Test #13:

score: 0

Accepted

time: 91ms

memory: 94356kb

input:

7739876803

output:

456270136

result:

ok single line: '456270136'

Test #14:

score: 0

Accepted

time: 250ms

memory: 95320kb

input:

80754680817

output:

4304423738

result:

ok single line: '4304423738'

Test #15:

score: 0

Accepted

time: 1107ms

memory: 95484kb

input:

1000000000000

output:

48366248808

result:

ok single line: '48366248808'

Test #16:

score: 0

Accepted

time: 514ms

memory: 94684kb

input:

300000000000

output:

15176932897

result:

ok single line: '15176932897'

Test #17:

score: 0

Accepted

time: 697ms

memory: 95340kb

input:

500000000000

output:

24808936807

result:

ok single line: '24808936807'

Test #18:

score: 0

Accepted

time: 873ms

memory: 94412kb

input:

700000000000

output:

34300642547

result:

ok single line: '34300642547'

Test #19:

score: 0

Accepted

time: 950ms

memory: 95320kb

input:

790673894439

output:

38570752521

result:

ok single line: '38570752521'