程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> NYOJ 476 誰是英雄(唯一素因子分解定理)

NYOJ 476 誰是英雄(唯一素因子分解定理)

編輯：關於C++

題目描述

十個數學家(編號0-9)乘氣球飛行在太平洋上空。當橫越赤道時，他們決定慶祝一下這一壯舉。於是他們開了一瓶香槟。不幸

的是，軟木塞在氣球上打了一個洞，氫氣洩漏，氣球開始下降，眼看就要落入海中，所有人將要被鲨魚吃掉。

但是尚有一線生機--若其中一人犧牲自己跳下去的話，那他的朋友們還能多活一會兒。但仍然有一個問題存在--誰

跳下去？所以他們想了一個非常公平的辦法來解決這個問題--首先，每人寫一個整數ai；然後計

算出a1×a2×a3×a4×……×a10的積的約數的個數N。例如，6的約數有4個（1、2、3、6），則N為4。這位犧牲自

己的英雄將由N的個位數來決定（編號為N的個位數的人要跳下去）。你的任務是求出N。

輸入T(T<=10)組測試數據。
十個整數ai(1≤ai≤10000)。輸出N的個位數樣例輸入

1
1 2 6 1 3 1 1 1 1 1

樣例輸出

題目分析：

唯一素因子分解問題，對於任意一個數n，都可以表示為：n=p[0]^a[0]*......*p[i]^a[i]*......*p[n]^a[n]，其中p[i]是素數，a[i]是整數>0，而n的約數的個數sum為，sum=(a[0]+1)*.....*(a[i]+1)*......(a[n]+1)。

AC代碼：

/**
  *@xiaoran
  *唯一素因子分解，n的約數個數為PI(a[i]+1)
  *res=(a[0]+1)*(a[1]+1)*...*(a[n]+1),其中a[i]均為素數
  */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
int a[10000];
int main()
{
    int t,n;
    cin>>t;
    while(t--){
        int res=1,x,k,m=0;
        memset(a,0,sizeof(a));
        for(int i=0;i<10;i++){
            cin>>n;
            if(m