1篇の素数のふるいの法と因子の数を求めると小さい技巧について説明します

次は直接質問します:(この2つの問題はすべてテクニックの問題です!!)1:HDU----1215题目この考え方:直接暴力はすべての数の因子と时会Tを求めて、だから更に因子と时を求めて少し聡明で、具体的な注釈はコードを见ます.

#include
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
",vis[n]);
}
int main()
{
    int t;
    scanf("%d",&t);
    init();
    while(t--){
        solve();
    }
}

HDU---1262題目この構想:まず範囲内の素数を表にし、それから隣接する最近の2つの数を選ぶので、真ん中から探す必要がある.
コードは次のとおりです.

#include
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
",vis[i]);
            if(!vis[i] && !vis[n-i])
                break;
        }
        printf("%d %d
",i,n-i);
    }
}

因子logNを求めるアルゴリズムを添付する.

#include
#include
#include
#include
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)    .
}