QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#48136	#4634. Factor	DerekFeng	AC ✓	1622ms	57208kb	C++	754b	2022-09-11 19:49:24	2022-09-11 19:49:26

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 19:49:26]
评测

测评结果：AC
用时：1622ms
内存：57208kb

查看

[2022-09-11 19:49:24]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
ll n,ans;bool f[N+4];
int tot,pri[N+4],num[N+4];
void init(){
	for(int i=2;i<=N;i++){
		if(!f[i])pri[++tot]=i;
		for(int j=1;j<=tot&&pri[j]*i<=N;j++){
			f[pri[j]*i]=1;
			if(i%pri[j]==0)break;
		}
	}for(int i=2;i<=N;i++)num[i]=num[i-1]+(!f[i]);
}
void sol(int p,ll V,ll S){
	if(pri[p]>S+1||V*pri[p]>n)return;
	if(V*pri[p]*pri[p]<=n){
		ll pw=1,sum=1;
		for(int tc=0;V<=n;tc++){
			if(tc>0){
				int pos=min(n/V,S*sum+1);
				if(pos>pri[p])ans+=num[pos]-num[pri[p]];
				if(tc>1)ans++;
			}
			sol(p+1,V,S*sum);
			V*=pri[p],pw*=pri[p],sum+=pw;
		}
	}
}
int main(){
	scanf("%lld",&n),init();
	ans=n>1?2:1,sol(1,1,1),printf("%lld",ans);
}

源文件, 语言: C++

詳細信息

Test #1:

score: 100

Accepted

time: 53ms

memory: 57072kb

input:

output:

result:

ok single line: '5'

Test #2:

score: 0

Accepted

time: 50ms

memory: 57104kb

input:

output:

result:

ok single line: '9'

Test #3:

score: 0

Accepted

time: 68ms

memory: 56812kb

input:

output:

result:

ok single line: '17'

Test #4:

score: 0

Accepted

time: 61ms

memory: 56892kb

input:

output:

result:

ok single line: '4'

Test #5:

score: 0

Accepted

time: 59ms

memory: 56736kb

input:

output:

result:

ok single line: '26'

Test #6:

score: 0

Accepted

time: 49ms

memory: 56888kb

input:

output:

result:

ok single line: '130'

Test #7:

score: 0

Accepted

time: 65ms

memory: 56796kb

input:

output:

result:

ok single line: '806'

Test #8:

score: 0

Accepted

time: 59ms

memory: 56724kb

input:

output:

result:

ok single line: '10905'

Test #9:

score: 0

Accepted

time: 68ms

memory: 56792kb

input:

output:

result:

ok single line: '95960'

Test #10:

score: 0

Accepted

time: 49ms

memory: 56796kb

input:

output:

result:

ok single line: '494209'

Test #11:

score: 0

Accepted

time: 57ms

memory: 56744kb

input:

51133311

output:

result:

ok single line: '3851066'

Test #12:

score: 0

Accepted

time: 66ms

memory: 56692kb

input:

607519174

output:

40319008

result:

ok single line: '40319008'

Test #13:

score: 0

Accepted

time: 101ms

memory: 56836kb

input:

7739876803

output:

456270136

result:

ok single line: '456270136'

Test #14:

score: 0

Accepted

time: 334ms

memory: 57208kb

input:

80754680817

output:

4304423738

result:

ok single line: '4304423738'

Test #15:

score: 0

Accepted

time: 1622ms

memory: 56936kb

input:

1000000000000

output:

48366248808

result:

ok single line: '48366248808'

Test #16:

score: 0

Accepted

time: 695ms

memory: 56936kb

input:

300000000000

output:

15176932897

result:

ok single line: '15176932897'

Test #17:

score: 0

Accepted

time: 991ms

memory: 56920kb

input:

500000000000

output:

24808936807

result:

ok single line: '24808936807'

Test #18:

score: 0

Accepted

time: 1266ms

memory: 56852kb

input:

700000000000

output:

34300642547

result:

ok single line: '34300642547'

Test #19:

score: 0

Accepted

time: 1380ms

memory: 56920kb

input:

790673894439

output:

38570752521

result:

ok single line: '38570752521'