前言
思路
显然$p$,$q$都是质数
因为时限$2s$考虑枚举质数,枚举过程如代码
$WA$最后一个测试点很多次记录一下
Code
// Problem: D - 250-like Number
// Contest: AtCoder - AtCoder Beginner Contest 250
// URL: https://atcoder.jp/contests/abc250/tasks/abc250_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false);
#define CIT cin.tie(0);
#define COT cout.tie(0);
#define ll unsigned long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)
typedef priority_queue<int,vector<int>,greater<int>> Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 2e7+5000,INF = 0x3f3f3f3f;
const double eps = 1e-5;
struct node{
int to,val;
};
int st[N];
unsigned long long primes[N];
int cnt = 0;
vector<ll> v;
multiset<ll> s;
int idx;
// ll v[N];
bool is_primes(ll x){
for(ll i = 2; i<=x/i;i++){
if(x%i == 0)return false;
}
return true;
}
void solve(){
ll n;cin>>n;
for(ll i = 2;i<=1e6;i++){
if(is_primes(i))
v.pb(i);
}
ll ans = 0 ;
ll temp;
for(auto it = v.begin();it!=v.end()-1;it++){
if(pow(*(it+1),3) <= n/(*it)){
temp = n /(*it);
temp = pow(temp,1.0/3);
ans += (lower_bound(all(v),temp)- it);
if(pow(*lower_bound(all(v),temp),3 )* *it > n){
ans--;
}
}
}
cout<<ans<<endl;
// cout<<l<<" "<<r<<endl;
}
signed main(){
// get_pri();
// sort(all(v));
// cout<<cnt<<endl;//
// cout<<v[1]<<" "<<v[2]<<endl;
// cout<<v.size()<<endl;
solve();
return 0 ;
}
昨天尝试打了一下,不出意料的只过了两题- -
从d题开始思路就没有了
还是得多练练hh
空想和行动有很大的鸿沟,大佬已经越过这一步了。下面就是弯道超车了QAQ
谢谢大佬的鼓励!!!!!Orz