「プロジェクトオイラー問148」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問148 - (2015/12/15 (火) 01:20:38) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20148

パスカルの三角形の１０億段目までに7で割り切れない数はいくつあるか答える問題。
とりあえず素朴に一行単位でまとめて計算。
計算時間３分。

 #include<stdio.h>
 #include<vector>
 #include<iostream>
 const int LIMIT=10000*10000*10;
 int main(){
 	__int64 n7=7;
 	__int64 ans=0;
 	std::vector<__int64> vec,vec7,vec7_2;
 	vec.push_back(0);
 	vec7.push_back(6);
 	vec7_2.push_back(6);
 	
 	for(int i=1;i<=LIMIT;i++){
 		int m=1;
 		int dell=0;
 		for(int j=vec.size()-1;j>=0;j--){
 			dell+=(vec[j]*m*vec7[j]);
 			m*=(vec[j]+1);
 		}
 		ans+=(i-dell);
 		
 		for(int j=0;j<vec7.size();j++){
 			vec7[j]--;
 		}
 		for(int j=0;j<vec.size();j++){
 			if(vec7[j]==-1){
 				if(j==0)vec[j]++;
 				vec7[j]=vec7_2[j];
 				if(vec[j]==7){
 					vec[j]=0;
 					if(vec.size()<=j+1){
 						n7*=7;
 						vec.push_back(1);
 						vec7_2.push_back(n7-1);
 						vec7.push_back(n7-1);
 						break;
 					}else{
 						vec[j+1]++;
 					}
 				}
 			}
 		}
 	}
 	std::cout<<"ans="<<ans<<"\n";
  }