TIOJ 1351 魔法使的條件

TIOJ 1351 魔法使的條件

題目概述:

給一個數字k，求 因數總和 與 因數個數 的乘積。

思路:

因數個數可能大家會比較熟悉，就把質因數分解後的指數加一然後相乘就是了?

那因數總和呢?

這邊直接給個例子來說明~

假設k=12=22*31

因數總和=(20+21+22)*(30+31)

因數個數=(2+1)*(1+1)

AC code:

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define maxn 3300

#define endl '\n'

bool np[maxn+5]={1,1};

vector<int> p;

main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   for(int i=2;i<=maxn;++i)

   {

       if(!np[i]){

           p.push_back(i);

           for(int j=i*i;j<=maxn;j+=i) np[j]=1;

       }

   }

   int T;cin>>T;

   while(T--)

   {

       int n;cin>>n;

       int tp=n,r=0;

       long long sum=1,num=1;

       while(tp>1)

       {

           if(r==p.size()){

               sum*=(tp+1);num*=2;break;

           }

           int ct=0,x=1,sm=1;

           while(tp%p[r]==0){

               ct++;tp/=p[r];x*=p[r];sm+=x;

           }

           if(ct) sum*=sm,num*=(ct+1);

           r++;

       }

       cout<<sum*num<<endl;

   }

}

如果沒有想到上面給的因數總和的算法

下面也給出DFS找出所有因數的作法

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define maxn 10000000

//#define int long long

#define endl '\n'

bool np[maxn+5]={1,1};

vector<int> p;

struct P{

   int pri,cnt;

};

vector<P> ans;

long long sum;

void dfs(int h,int s)

{

   if(h==ans.size()) {sum+=s;return ;}

   P t=ans[h];

   int tp=1;

   for(int i=0;i<=t.cnt;++i){

       dfs(h+1,s*tp);

       tp*=t.pri;

   }

}

main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   for(int i=2;i<=maxn;++i)

   {

       if(!np[i]){

           p.push_back(i);

           for(int j=i+i;j<=maxn;j+=i) np[j]=1;

       }

   }

   int T;cin>>T;

   while(T--)

   {

       ans.clear();

       int n;cin>>n;

       int tp=n,r=0;

       while(tp>1)

       {

           int ct=0;

           while(tp%p[r]==0){

               ct++;tp/=p[r];

           }

           if(ct) ans.push_back({p[r],ct});

           r++;

       }

       sum=0;

       dfs(0,1);

       int num=1;

       for(int i=0;i<ans.size();++i) num*=(ans[i].cnt+1);

       cout<<sum*num<<endl;

   }

}

對了

可以發現上下兩份作法，上面的質數只有開到3300，所以速度會快很多!!

我們知道一個數n要檢查它是否為質數只要檢查過小於sqrt(n)的質數是否整除

因為33002=10890000maxn，所以當k掃過3300內的的質數，若還有沒除盡的就代表它是質數，且它的指數會是1，因為2次方就會大於maxn，就可以利用這個特性來做。