簡単なので
2<=a<=100000,2<=b<=100000
計算時間 0.43sec
答え 9981236306
と挑戦してみた。
答えあってるかな。
a0を素因数分解した時、
素因数2の数を1次元めに
素因数3の数を2次元目に
、、、
とベクトルでaを表すと、aのある数a0とa1はa0^nとa1^mのベクトルが重なるかどうか、つまりベクトルの定数倍の問題に帰着することを利用して解。
#include<stdio.h>
#include<map>
#include<set>
#include<iostream>
const int LIMIT=100000;
int main(){
int bads[LIMIT+1]={0};
std::map<int,__int64> memo;
std::set<int> all;
for(int i=1,p=1;p<=LIMIT*2;p*=2,i++){
for(int j=2;j<=LIMIT;j++){
all.insert(i*j);
}
memo[i]=all.size();
std::cout<<"("<<i<<" "<<all.size()<<"\n";
}
__int64 ans=0;
for(int i=2;i<=LIMIT;i++){
if(bads[i]==0){
__int64 p=i;
int count=0;
while(p<=LIMIT){
bads[(int)p]=1;
count++;
p*=i;
}
ans+=memo[count];
}
}
std::cout<<"ans="<<ans<<"\n";
}
最終更新:2014年12月01日 08:09