先不说你这复杂度高得离谱,你这 AC 函数求的是最大因子而不是最大质因子
by houwz351 @ 2024-04-25 17:12:54
@[houwz351](/user/807266) 50了
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
int zs(int a)
{
if(a==1)
return 0;
for(int i=2;i*i<=a;i++)
{
if(a%i==0)
return 0;
}
return 1;
}
int AC(int a)
{
if(zs(a)==1)
return a;
int ans=0;
for(int i=a-1;i>=1;i--)
{
if(a%i==0)
ans=i;
}
return ans;
}
main()
{
int n,b;
int ans=0;
cin>>n>>b;
for(int i=0;i<n;i++)
{
if(AC(i)<=b)
ans++;
}
cout<<ans;
return 0;
}
```
by 2345A @ 2024-04-25 18:21:31
时间复杂度太高了,改了输出对了但是后面七个点超时,自己优化下吧。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int cns = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0') {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
cns = cns * 10 + ch - '0';
ch = getchar();
}
return cns * f;
}
int zs(int a) {
if(a==1)return 0;
for(int i=2; i*i<=a;i++) {
if(a%i==0)return 0;
}
return 1;
}
int AC(int a){
if(zs(a)==1)return a;
for(int i=a-1; i>=2;i--) {//改了
if(a%i==0&&zs(i))return i;//改了
}
}
main() {
int n,b;
int ans=1;
n=read();b=read();
for(int i=2;i<=n;i++){
if(AC(i)<=b)ans++;
}
cout<<ans;
return 0;
}
```
@[2345A](/user/565070)
by xyx404 @ 2024-04-25 18:53:55