程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ 476 誰是英雄(唯一素因子分解定理)

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

編輯:C++入門知識

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


題目描述

 

十個數學家(編號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
樣例輸出
9

題目分析:

唯一素因子分解問題,對於任意一個數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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved