题目描述
blablabla
样例
#include <iostream>
using namespace std;
typedef long long ll;
ll ans;
bool isprime(ll n){
if(n == 1) return false;
for(ll i = 2; i*i <= n; ++ i)
if(n % i == 0) return false;
return true;
}
////////////////////太完美了,,优化到极致,,先是复杂度根号n,然后每一个合法数都判其对称的数,最后看原数n是否为质数
int main()
{
ll n; cin >> n;
for(ll i = 2; i*i <= n; ++ i){
if(n % i == 0){
if(isprime(i)) ans ++;////////////////此时求它的一个对称的数,检查是否满数组要求
if(i*i != n && isprime(n/i)) ans ++;//////--------既不是中间数,又是满足的质数,就把对称数加入,节省时间复杂度
}
}
if(isprime(n)) ans++;
cout << ans;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla