51nod1189

1068 단어
링크:클릭하여 링크 열기
제목: 1/N!1/X+1/Y, 조건을 만족시키는 정수해의 수량을 구하는 N을 제시한다.예를 들어 N = 2, 1/2 = 1/3 + 1/6, 1/2 = 1/4 + 1/4 입니다.수량이 많을 수 있으므로 Mod 10^9 + 7 출력
코드:
#include <iostream>
#include <cmath>
#include <cstring>
#define mod 1000000007
using namespace std;
long long prime[1000005],num[1000005];
int main(){
    long long i,j,k,n,sum,temp,flag,sumsum;
    k=0;
    memset(prime,0,sizeof(prime));
    for(i=2;i<=1000000;i++){
    if(!prime[i])
    num[k++]=i;
    for(j=0;j<k&&num[j]*i<=1000000;j++){
    prime[num[j]*i]=1;
    if(i%num[j]==0)
    break;
    }
    }
    while(cin>>n){
    sumsum=1;
    for(i=0;num[i]<=n;i++){
    temp=n;sum=0;
    while(temp){
        temp/=num[i];
        sum+=temp;
    }
    flag=2*sum+1;               //    http://blog.csdn.net/stay_accept/article/details/47188133
    sumsum=(sumsum*flag)%mod;
    }
//    cout<<sumsum<<endl;
    cout<<((sumsum+1)%mod)*(500000004%mod)%mod<<endl;  //        
    }
    return 0;
}
</span>

좋은 웹페이지 즐겨찾기