下面直接上题:（这两道题都是技巧题!!!）
1: HDU ---- 1215 题目在此
思路: 直接暴力求每一个数的因子和时会T,所以再求因子和时需要耍点小聪明,具体注释看代码.
#include<bits/stdc++.h>
int vis[maxn];
void init()
{
for(int i=1;i<=maxn;i++) //首先每个数都肯定有1这个因子.
vis[i]=1;
for(int i=2;i<=maxn/2;i++){ //然后大循环,因为因子最大就是2*x=这个数,所以循环到这就行了.
for(int j=i*2;j<=maxn;j+=i){ //因为每一个对应的倍数它的因子一定有i.
vis[j]+=i; //加减运算的时间比乘除运算的时间少很多(如果你用一般的取余法会T的,而加减法可以做到的就不用取余的,只不过要反着来!!)
}
}
}
void solve()
{
int n;
cin >> n;
printf("%d\n",vis[n]);
}
int main()
{
int t;
scanf("%d",&t);
init();
while(t--){
solve();
}
}
HDU --- 1262 题目在此
思路: 先对范围内的素数进行打表,然后因为是要选出相邻最近的两个数,所以需要从中间开始找.
代码如下:
#include<bits/stdc++.h>
int vis[maxn];
void init() //素数打表,这个经常用到.
{
vis[0]=1;
vis[1]=1;
for(int i=2;i<=maxn;i++){
if(!vis[i]){ //这样才行,即素数为0,非素数为1.（反着来有点难受）.
vis[i]=0;
for(int j=2*i;j<=maxn;j+=i)
vis[j]=1;
}
}
}
int main()
{
init();
int i,n;
while(scanf("%d",&n)!=EOF){
for(i=n/2;i>=0;i--){ //从中间开始找,如果能找到,则肯定是相邻最近的两个素数,所以输出.
//printf("%d\n",vis[i]);
if(!vis[i] && !vis[n-i])
break;
}
printf("%d %d\n",i,n-i);
}
}
附上一个求因子logN的算法.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e6;
int pre[maxn]; //存要求数的因子有哪些.
int main()
{
int k;
cin >> k ;
for(int i=1;i*i<=k;i++){ //精华就在 i*i <= k 这里!
if(k%i==0){
pre[cnt++] = i;
pre[cnt++] = k/i;
//cout << i << endl << k/i << endl;
}
} // pre中存的就是k的所有因子,且时间复杂度相比普通求法O(n)低很多了.
}
