読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

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;
}