QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#48048	#4634. Factor	Pure_Furies	AC ✓	1279ms	95440kb	C++23	685b	2022-09-11 13:45:27	2022-09-11 13:45:30

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 13:45:30]
评测

测评结果：AC
用时：1279ms
内存：95440kb

查看

[2022-09-11 13:45:27]
提交

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++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 64ms

memory: 95400kb

input:

output:

result:

ok single line: '5'

Test #2:

score: 0

Accepted

time: 73ms

memory: 95316kb

input:

output:

result:

ok single line: '9'

Test #3:

score: 0

Accepted

time: 85ms

memory: 94040kb

input:

output:

result:

ok single line: '17'

Test #4:

score: 0

Accepted

time: 84ms

memory: 95412kb

input:

output:

result:

ok single line: '4'

Test #5:

score: 0

Accepted

time: 74ms

memory: 95320kb

input:

output:

result:

ok single line: '26'

Test #6:

score: 0

Accepted

time: 99ms

memory: 94444kb

input:

output:

result:

ok single line: '130'

Test #7:

score: 0

Accepted

time: 66ms

memory: 94444kb

input:

output:

result:

ok single line: '806'

Test #8:

score: 0

Accepted

time: 92ms

memory: 95272kb

input:

output:

result:

ok single line: '10905'

Test #9:

score: 0

Accepted

time: 75ms

memory: 94804kb

input:

output:

result:

ok single line: '95960'

Test #10:

score: 0

Accepted

time: 82ms

memory: 95440kb

input:

output:

result:

ok single line: '494209'

Test #11:

score: 0

Accepted

time: 80ms

memory: 95024kb

input:

51133311

output:

result:

ok single line: '3851066'

Test #12:

score: 0

Accepted

time: 81ms

memory: 94992kb

input:

607519174

output:

40319008

result:

ok single line: '40319008'

Test #13:

score: 0

Accepted

time: 100ms

memory: 94600kb

input:

7739876803

output:

456270136

result:

ok single line: '456270136'

Test #14:

score: 0

Accepted

time: 227ms

memory: 95212kb

input:

80754680817

output:

4304423738

result:

ok single line: '4304423738'

Test #15:

score: 0

Accepted

time: 1279ms

memory: 95268kb

input:

1000000000000

output:

48366248808

result:

ok single line: '48366248808'

Test #16:

score: 0

Accepted

time: 559ms

memory: 94184kb

input:

300000000000

output:

15176932897

result:

ok single line: '15176932897'

Test #17:

score: 0

Accepted

time: 698ms

memory: 94048kb

input:

500000000000

output:

24808936807

result:

ok single line: '24808936807'

Test #18:

score: 0

Accepted

time: 882ms

memory: 94952kb

input:

700000000000

output:

34300642547

result:

ok single line: '34300642547'

Test #19:

score: 0

Accepted

time: 955ms

memory: 94804kb

input:

790673894439

output:

38570752521

result:

ok single line: '38570752521'