NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2014高中組決賽
 npsc 2014 高中決賽 C.北斗遺跡

作者 主題: npsc 2014 高中決賽 C.北斗遺跡  (閱讀 2186 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
npsc 2014 高中決賽 C.北斗遺跡
« 於: 一月 23, 2015, 10:52:58 pm »

求K1 * K2 的所有因數的個數
因k1,k2<=10^6,建<=1000000的質數表
kk = k1*k1會大於 2^32,所以設為 long long
將 kk 化為質因數乘積: p1^n1 * p2^n2 .... pj^nj
則所有因數的個數為: (n1+1)*(n2+1) .... *(nj+1)

代碼: [選擇]
/*
NPSC 2014 高中組決 C. 北斗遺跡 , 求K1 * K2 的所有因數

類 ZJ:d756: 10290 - {Sum+=i++} to Reach N   N的奇數因數共有幾個? 且更簡單
*/
#include <iostream>
#include <cmath>
#define MaxN 1000000
using namespace std;
bool m[MaxN];
long long p[78500]; // 1000000 內的質數 78498個
int ps;
void genp() //建 <1000000的質數表
{
int i,j,k,q=int(sqrt(MaxN));
p[0]=2;
for(i=3; i<q; i+=2) // 只設定奇數
{
if(!m[i]) for(k=2*i, j=i*i; j<MaxN; j+=k ) m[j]=true;
}
for(ps=1, i=3; i<MaxN; i+=2 )
if(!m[i]) p[ps++] = i;
/* 印質數個數、前200
cout <<"tot:"<<ps<<endl;
for(j=0;j<200;++j)
{
cout <<p[j]<<" ";
if((j+1)%10==0) cout << endl;
}
*/
}
int main( )
{
   genp();
long long k1,k2,kk;
int cnt, i, t, ans,line=0;
cin >>t;
while( t-- )
{
cin >> k1 >> k2;
kk = k1*k2;
if(kk==1) cout << 1 << endl;
else
{
ans=1;
for(i=0;i<ps && kk!=1;++i)
{
for( cnt=1; kk%p[i]==0; ++cnt ) kk/=p[i];
ans *= cnt;
}
if( kk!=1 ) ans *= 2;
cout << ans << endl;
}
}   
   return 0;
}
/*
5
1 2
2 3
4 7
8 6
101 6
-------------
2
4
6
10
8
*/

記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2014高中組決賽
 npsc 2014 高中決賽 C.北斗遺跡