原始题目

B - 105

• Time limit : 2sec / Memory limit : 1000MB

• Score: 200 points

Problem Statement

The number 105 is quite special - it is odd but still it has eight divisors. Now, your task is this: how many odd numbers with exactly eight positive divisors are there between 1 and N (inclusive)? ### Constraints - N is an integer between 1 and 200 (inclusive).

Input

Input is given from Standard Input in the following format:

N

Output

Print the count.

Sample Input 1

105

Sample Output 1

1

• Among the numbers between 1 and 105, the only number that is odd and has exactly eight divisors is 105.

Sample Input 2

7

Sample Output 2

0

• 1 has one divisor. 3, 5 and 7 are all prime and have two divisors. Thus, there is no number that satisfies the condition.

题目大意

给定n，求1到n恰好又8个因数的数字有多少个

集体思路

• 水题，预处理一下因子个数，再求一下前缀和就行。

解题代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define mp make_pair
#define np next_permutation
#define pb push_back
#define all(x) (x.begin(),x.end())
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
 
#define fi first
#define se second 
using namespace std;
const int maxn=1e4+5;
const int maxl=26;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
 
int cnt[maxn],ans[maxn];
void solve(){
	rep(i,1,300) cnt[i]++;
	rep(i,2,300){
		for(int j=1;j*i<=300;j++){
			cnt[i*j]++;
		}
	}
	int ccnt=0;ans[0]=0;
	rep(i,1,300) {
		if(cnt[i]==8 and (i&1)){
			ans[i]=++ccnt;
		}
		else ans[i]=ccnt;
	}
	rep(i,1,300) {
//		cout<<"ans["<<i<<"]="<<ans[i]<<endl;
	}
}
 
int a,b;
int main(){
	ios::sync_with_stdio(false); 
	solve();
	int n;
	while(cin>>n)
		cout<<ans[n]<<endl;
} 

收获与反思

无