AtCoderのARC
次のARCの問題へ
前のARCの問題へ
ARC034-C 約数かつ倍数
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 2");
//2
}
else if (InputPattern == "Input2") {
WillReturn.Add("15 4");
//2592
}
else if (InputPattern == "Input3") {
WillReturn.Add("1000000 999900");
//21398499
}
else if (InputPattern == "Input4") {
WillReturn.Add("1000000000 999999900");
//745508745
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
const long Hou = 1000000007;
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long A = wkArr[0];
long B = wkArr[1];
var AllSoinsuuDict = new Dictionary<long, long>();
for (long I = B + 1; I <= A; I++) {
var CurrSoinsuuDict = DeriveSoinsuuDict(I);
foreach (var EachPair in CurrSoinsuuDict) {
if (AllSoinsuuDict.ContainsKey(EachPair.Key) == false) {
AllSoinsuuDict[EachPair.Key] = 0;
}
AllSoinsuuDict[EachPair.Key] += EachPair.Value;
}
}
long Answer = 1;
foreach (long EachLong in AllSoinsuuDict.Values) {
Answer *= EachLong + 1;
Answer %= Hou;
}
Console.WriteLine(Answer);
}
// 素因数分解し、指数[素数]なDictを返す
static Dictionary<long, long> DeriveSoinsuuDict(long pTarget)
{
var WillReturn = new Dictionary<long, long>();
long CurrVal = pTarget;
// ルートより大きい数を、素因素に持つとしても、1つだけのため
// ルートまで試し割りを行い、素因数が残っていたら、追加する
for (long I = 2; I * I <= pTarget; I++) {
if (CurrVal % I > 0) continue;
WillReturn[I] = 0;
while (CurrVal % I == 0) {
WillReturn[I]++;
CurrVal /= I;
}
if (CurrVal == 1) break;
}
// 素因数が残っている場合
if (CurrVal > 1) {
WillReturn[CurrVal] = 1;
}
return WillReturn;
}
}
解説
A=15 , B=10 で考察すると
2*3*4*5*6*7*8*9*10*11*12*13*14*15 の約数かつ
2*3*4*5*6*7*8*9*10 の倍数
が何通りあるかなので
11から15を素因数分解し、
(指数+1)の総積が解だと分かります。