csdn英雄会hero題解のF(X)
1690 ワード
同じ:http://hao666.info/blog/?p=31
タイトル
タイトルの詳細:
我々はF(x)がxを満たすことを定義する mod(a*b)==0のようなa,bのグループ数.今nをあげます.F(n)を求める必要があります.
入力形式:
複数のデータのセットで、各グループの最初の行には整数n、0出力フォーマット:
各グループは1行出力し,条件を満たす(a,b)対数
問題の説明:
入力サンプル
1
2
3
4
出力サンプル:
1
3
3
6
説明する
第一グループ:(1,1)
2番目のグループ: (1,1) (1,2) (2, 1)
3番目のグループ: (1,1) (1,3) (3,1)
4番目のグループ: (1,1) (1,2) (1, 4) (2, 1) (2,2) (4,1)
解法
簡単:
xのすべての質量因子を求め、各質量因子の個数factors[]を統計し、factors[i]はi番目の質量因子の個数を表す.
ではmulti((factors[i]+1)*(factors[i]+1) /2)求めている
コード#コード#
タイトル
タイトルの詳細:
我々はF(x)がxを満たすことを定義する mod(a*b)==0のようなa,bのグループ数.今nをあげます.F(n)を求める必要があります.
入力形式:
複数のデータのセットで、各グループの最初の行には整数n、0
各グループは1行出力し,条件を満たす(a,b)対数
問題の説明:
入力サンプル
1
2
3
4
出力サンプル:
1
3
3
6
説明する
第一グループ:(1,1)
2番目のグループ: (1,1) (1,2) (2, 1)
3番目のグループ: (1,1) (1,3) (3,1)
4番目のグループ: (1,1) (1,2) (1, 4) (2, 1) (2,2) (4,1)
解法
簡単:
xのすべての質量因子を求め、各質量因子の個数factors[]を統計し、factors[i]はi番目の質量因子の個数を表す.
ではmulti((factors[i]+1)*(factors[i]+1) /2)求めている
コード#コード#
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <map>
void getFactors(long long i,std::map<long long,int>&ret){
if(i<2)
return ;
long long s=2;
long long e=(long long)sqrt((double)i);
int x=0;
while(0==i%s){
++ret[s];
i/=s;
}
++s;
while(s<=e){
while(0==i%s){
++ret[s];
i/=s;
}
s+=2;
}
if(i!=1)
++ret[i];
}
int main(){
long long i=0;
while(std::cin>>i){
std::map<long long,int>fs;
getFactors(i,fs);
long long ret=1;
for(std::map<long long,int>::iterator it=fs.begin();it!=fs.end();++it)
ret*=(it->second+2)*(it->second+1)/2;
std::cout<<ret<<std::endl;
}
}