C. 质因子分解

#include<bits/stdc++.h>
using namespace std;
int prime(int x)
{
int i;
if(x<2)
return 0;//小于2的肯定不是质数
else
{
for(i=2;i*i<=x;i++)//从2开始到sqrt(x)枚举
if(x%i==0)
return 0;//如果可以整除，那么一定不是质数
return 1;
}
}//质数判别函数
int n,cnt[100000];
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
int j=i;//找个替代品
for(int k=1;k<=i;k++)
while((j%k==0) && (prime(k)==1) && j>1)//如果k是j的因子，并且k还是质数，也就是k是j的质因子，而且j>1
{
cnt[k]++;//计数++
j=j/k;//不停地除
}
}
for(int i=0;i<=n;i++)
if(cnt[i]!=0)//如果有这个质因子
cout<<i<<' '<<cnt[i]<<endl;
return 0;
}
/*
题解：
这道题4个要点：
1.怎么判别因子？
2.怎么判别质数？
3.怎么统计个数？
4.阶乘太大会爆unsigned long long怎么办？

解决办法也很简单：
1.用模运算%；
2.用自定义函数prime(x)；
3.用类似于桶排序的概念，用一个数组来统计个数；
即如果k是某个数的质因子，则count[k]++;
4.如果会爆内存，就一步一步算，不要一次性把结果算出来。
*/

D. 数的范围

#include<bits/stdc++.h>
using namespace std; 
const int N = 100010;
int n, q;
//从0到n - 1读入数据
int a[N];
//第一个二分算法:目的是找到第一个k的位置
int binary_search_l(int l, int r, int k)
{
int ans=-1;
while(l <= r)
{
int mid = (l + r) / 2;
if(a[mid] >= k)
{
if(a[mid] == k) ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
//第二个二分算法:目的是找到最后一个k的位置
int binary_search_r(int l, int r, int k)
{
int ans=-1;
while(l <= r)
{
int mid = (l + r) / 2;
if(a[mid] <= k)
{
if(a[mid] == k) ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
return ans;
}
int main()
{
scanf("%d%d", &n, &q);
for(int i = 0; i < n; i ++ ) cin>>a[i];

while(q -- ){

int k;
cin >> k;
int l = binary_search_l(0, n - 1, k);
if(l ==-1) cout<<"-1 -1\n";
//若ans==-1 ,说明没有找到k
else {
int r = binary_search_r(0, n - 1, k);
cout<<l<<' '<<r<<endl;
}
}
}
/*
题解：
这道题是一道练习二分搜索的题目，注意求解最后一个k的位置和第一个k的位置方法有所区别
还需注意，可能数组中并没有k，需要特殊判断
*/