大佬求调谢谢

常规
1
  1. 三质数

XJOI - 题目ID：1194100分

最新提交：

Time Limit Exceeded

0 分

历史最高：

Time Limit Exceeded

0 分

时间限制: 1000ms

空间限制: 131072kB

题目描述

时间限制：1s 空间：256M

题目描述：

一个数的约数也称为因子，比如11是66的因子，22是66的因子，66是66的因子。

质数只有两个因子，11和它本身

现在定义一种新的质数，三质数，三质数只有三个不同的因子。比如44是三质数，因为它有1,2,41,2,4三个因子。比如66不是三质数，因为66有1,2,3,61,2,3,6四个因子。现在有一些数，你需要判断他们是不是三质数。

输入格式：

第一行一个整数T，表示有T组测试数据。

每组测试数据输入一个整数n

输出格式：

对于每组测试数据，判断是否是三质数，如果是输出YES，否则输出NO

样例输入：

3 4 5 6

样例输出：

YES NO NO

1 <=� <=1012,数据组数不超过103 1 <=n <=1012,数据组数不超过103

我的代码：

#include<bits/stdc++.h>
using namespace std;
int ans=0,cnt=0;
int yinshu(int a){
  for(int i=1;i<=a;i++){
    if(a%i==0) ans++;
  }
  return ans;
}
int main(){
  int n;
  cin>>n;
  while(n--){
    int x;
    cin>>x;
    if(yinshu(x)==3) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
  }
}
5 个赞
2

emm，你的数字应该重复了吧（我看题目看了好久也没明白）
首先，要知道，一个数的因子的因子，也是这个数的因子
那么我们就可以推导出，三质数必须是完全平方数，且必须是质数的平方。
就这点你可以减少枚举量。

先对一个数组作预处理，如 a_i 表示i这个数是否为素数 这里的最大范围应该是n可能最大值。（欧拉筛法）这里的时间复杂度为 \Theta(n)
如判断这个数是否为完全平方数
如果是
{
判断这个数的平方根是否为素数，由于已经对数组做了预处理，因此时间复杂度为 $\Theta(1)$。
}
如果不是，那这个数就不是三质数

接着有一点很奇怪的，你原来的程序按理来说也是可以过的
数据组数不超过103，n也不超过1012，而你的时间复杂度为 \Theta(Tn)
我觉得有可能你复制的时候没有复制好
这道题目的实际范围应该是 ：T不超过10^3，n不超过10^12
那如果是这样我也不敢保证我刚才提到的算法是否能过，因为n实在是太大了
除此之外我一时半会也想不出其他跟高效的算法了

3 个赞
3

太有用了谢谢

3 个赞
4 
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,t,f;
	cin>>t;
	for(int i=1;i<=t;i+=1){
		cin>>n;
		long long a=sqrt(n);
		if(a*a!=n){
			cout<<"NO"<<endl;
			continue;
		}
		f=1;
		for(int j=2;j*j<=a;j++){
			if(n%j==0){
				f=0;
				break;
			}
		}
		if(f==1) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
			
		}
}

可以看看我这个，O(t*log(log(n)))的（应该是吧）

2 个赞
5

不是吧，要用大O表示法的话，平方根级别的应该是 O(n^\frac{1}{2}) 把

2 个赞
6

应该!

2 个赞
7

问一下，时间复杂度不是循环次数吗？

2 个赞
8

时间复杂度是个估计

3 个赞
9

#include<bits/stdc++.h>
using namespace std;
int main(){
int n;long long a;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
double sum=sqrt(a);
if(sum-floor(sum)!=0){
cout<<“NO”<<endl;
}
else{
int s=sqrt(a),x=0;
for(int i=s;i>=1;i–){
if(i-1==1){
break;
}
if(s%(i-1)==0){
cout<<“NO”;
x=1;
break;
}
}
if(x==0){
cout<<“YES”;
}
cout<<endl;
}
}
}

3 个赞
10

不一定

2 个赞
11

@yhxyd0324 那怎么算呢？还有，log(n)到底怎么算？

12

首先你要知道x^log x n == n, 然后你就可以去算了！！！（怎么和没说似的）。
一般时间复杂度是循环层数，蛋柿有一些有continue/break的例外。

具体的计算方法本人也不知道

1 个赞