結果

問題 No.8123 Calculated N !
ユーザー GOTKAKO
提出日時 2025-04-01 22:41:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 322 ms / 2,000 ms
コード長 5,437 bytes
コンパイル時間 2,324 ms
コンパイル使用メモリ 212,796 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-04-01 22:41:54
合計ジャッジ時間 6,961 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:150:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |         scanf("%lld", &N);
      |         ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//https://judge.yosupo.jp/submission/61551
//Um_nikさんのお借りしました.

#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(1234567);
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

int isqrt(ll n) {
	return sqrtl(n);
}

__attribute__((target("avx2"), optimize("O3", "unroll-loops")))
ll prime_pi(const ll N) {
	if (N <= 1) return 0;
	if (N == 2) return 1;
	const int v = isqrt(N);
	int s = (v + 1) / 2;
	vector<int> smalls(s);
	for (int i = 1; i < s; i++) smalls[i] = i;
	vector<int> roughs(s);
	for (int i = 0; i < s; i++) roughs[i] = 2 * i + 1;
	vector<ll> larges(s);
	for (int i = 0; i < s; i++) larges[i] = (N / (2 * i + 1) - 1) / 2;
	vector<bool> skip(v + 1);
	const auto divide = [](ll n, ll d) -> int { return (double)n / d;};
	const auto half = [](int n) -> int { return (n - 1) >> 1;};
	int pc = 0;
	for (int p = 3; p <= v; p += 2) if (!skip[p]) {
		int q = p * p;
		if ((ll)q * q > N) break;
		skip[p] = true;
		for (int i = q; i <= v; i += 2 * p) skip[i] = true;
		int ns = 0;
		for (int k = 0; k < s; k++) {
			int i = roughs[k];
			if (skip[i]) continue;
			ll d = (ll)i * p;
			larges[ns] = larges[k] - (d <= v ? larges[smalls[d >> 1] - pc] : smalls[half(divide(N, d))]) + pc;
			roughs[ns++] = i;
		}
		s = ns;
		for (int i = half(v), j = ((v / p) - 1) | 1; j >= p; j -= 2) {
			int c = smalls[j >> 1] - pc;
			for (int e = (j * p) >> 1; i >= e; i--) smalls[i] -= c;
		}
		pc++;
	}
	larges[0] += (ll)(s + 2 * (pc - 1)) * (s - 1) / 2;
	for (int k = 1; k < s; k++) larges[0] -= larges[k];
	for (int l = 1; l < s; l++) {
		ll q = roughs[l];
		ll M = N / q;
		int e = smalls[half(M / q)] - pc;
		if (e < l + 1) break;
		ll t = 0;
		for (int k = l + 1; k <= e; k++)
			t += smalls[half(divide(M, roughs[k]))];
		larges[0] += t - (ll)(e - l) * (pc + l - 1);
	}
	return larges[0] + 1;
}


long long mod = 1e9+7;
//入力が必ず-mod<a<modの時.
struct mint{
    long long v = 0;
    mint(){} mint(int a){v = a<0?a+mod:a;} mint(long long a){v = a<0?a+mod:a;}
    mint(unsigned long long a){v = a;}
    long long val(){return v;}

    mint &operator=(const mint &b) = default;
    mint operator-() const {return mint(0)-(*this);}
    mint operator+(const mint b){return mint(v)+=b;}
    mint operator-(const mint b){return mint(v)-=b;}
    mint operator*(const mint b){return mint(v)*=b;}
    mint operator/(const mint b){return mint(v)/=b;}

    mint operator+=(const mint b){
        v += b.v; if(v >= mod) v -= mod;
        return *this;
    }
    mint operator-=(const mint b){
        v -= b.v; if(v < 0) v += mod; 
        return *this;
    }   
    mint operator*=(const mint b){v = v*b.v%mod; return *this;}
    mint operator/=(mint b){
        if(b == 0) assert(false);
        int left = mod-2;
        while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
        return *this;
    }

    mint operator++(){*this += 1; return *this;}
    mint operator--(){*this -= 1; return *this;}
    mint operator++(int){*this += 1; return *this;}
    mint operator--(int){*this -= 1; return *this;}
    bool operator==(const mint b){return v == b.v;}
    bool operator!=(const mint b){return v != b.v;}
    bool operator>(const mint b){return v > b.v;}
    bool operator>=(const mint b){return v >= b.v;}
    bool operator<(const mint b){return v < b.v;}
    bool operator<=(const mint b){return v <= b.v;}

    mint pow(long long n){
        mint ret = 1,p = v;
        if(n < 0) p = p.inv(),n = -n;
        while(n){
            if(n&1) ret *= p;
            p *= p; n >>= 1;
        }
        return ret;
    }
    mint inv(){return mint(1)/v;}
};

int main(){
	startTime = clock();
	ll N;
	scanf("%lld", &N);

    int Need = 10'000'000;
    vector<bool> prime(Need+1,true);
    prime.at(0) = false; prime.at(1) = false;
    for(int i=2; i*i<=Need; i++){
        if(!prime.at(i)) continue;
        for(int k=i*i; k<=Need; k+=i) prime.at(k) = false;
    }

    mint answer = 1;
    long long al = 2;
    for(al=2; al<=min(N,(ll)Need); al++){
        if(prime.at(al) == false) continue;
        long long v = N;
        mint all = 0;
        while(v){
            all += v/al%mod;
            v /= al;
        }
        answer *= all+1;
    }
    al--;
    int ap = 1000;
    if(al < N){ 
        long long back = prime_pi(al);
        while(true){
            long long now = N/ap;
            if(now > al){
                long long p = prime_pi(now);
                answer *= mint(ap+1).pow(p-back);
                back = p;
            }
            ap--;
            if(ap == 0) break;
        }
    }
    cout << answer.v << endl; 
return 0;
    answer = 1;
    for(int i=2; i<=N; i++){
        if(prime.at(i) == false) continue;
        long long v = N;
        mint all = 0;
        while(v){
            all += v/i%mod;
            v /= i;
        }
        answer *= all+1;
    }
    cout << answer.v << endl;
	return 0;
}
0