PKU 2603 Brave balloonists
http://poj.org/problem?id=2603
10個の数字がある。この10個の数字を全てかけ合わせた数の約数の個数の1の位の数を求めろという問題。
因数分解して、約数の個数の公式を当てはめる。
なんだかブラックだったりユーモアがあったりする問題だと思いました。
typedef map<int,int> mii; mii merge(mii&a,mii&b){ mii ret; FOR(miter,a)ret[miter->F]+=miter->S; FOR(miter,b)ret[miter->F]+=miter->S; return ret; } bool pr[10000]; int npr[10000]; int num; mii conv(int t){ mii ret; rep(i,num){ if(t<npr[i])break; while(t && t%npr[i]==0){ ret[i]++; t/=npr[i]; } } return ret; } main(){ pr[0]=pr[1]=true; for(int i=2;i<10000;i++){ if(pr[i])continue; for(int j=2*i;j<10000;j+=i)pr[j]=true; } rep(i,10000)if(!pr[i])npr[num++]=i; mii ans; rep(i,10){ int t; cin>>t; mii fact=conv(t); ans=merge(ans,fact); } int tt=1; FOR(miter,ans){ tt=(tt*(miter->S+1))%10; } cout<<tt<<endl; }