POJ 2603 : Brave balloonists
問題リンク:2603 -- Brave balloonists
問題概要:
1以上10000以下の整数が10個与えられる
これらの積の約数の数の最後の桁を出力せよ
解法:
10個の整数をそれぞれ素因数分解し、各素因数の数を数える
あとはそれらの数の積をとり、最後の一桁だけ出力する
コード:
#define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define IINF (INT_MAX) #define all(n) (n).begin(),(n).end() using namespace std; typedef long long ll; map<ll,int> prime_factor(ll n) { map<ll,int> res; for(int i=2;i*i<=n;i++) { while(n % i == 0) { ++res[i]; n /= i; } } if(n != 1)res[n] = 1; return res; } int main(){ map<ll,int> pfs; int v; rep(_,10){ scanf("%d",&v); map<ll,int> pf = prime_factor(v); for( map<ll,int>::iterator it = pf.begin(); it != pf.end(); it++ ) if( it->first != 1 )pfs[it->first] += it->second; } ll ans = 1; for(map<ll,int>::iterator it=pfs.begin();it!=pfs.end();it++){ ( ans *= (ll)(it->second+1) ) %= 10LL; } printf("%d\n",ans); return 0; }