A simple Blog for wyx I've been down the bottle hoping.
SRM 552 数学
发表于: | 分类: Oi | 评论:0 | 阅读:61

250 没看
500 请见官方题解 一看就知道怎么做但是根本不想写系列
900
神奇的数学题

给定$Max$,以及$n$, 求 $[1,n]$ 内有多少个数字能用 $Max$ 以内的质数的奇数次幂表示

$Max \le 10^6, n \le 10^10$

首先线性筛出 $[1,Max]$ 内的所有素数,标号 $[1,m]$

然后我们大力算一下就行辣

每次考虑当前素数对答案的贡献,然后把$y$ 除去当前素数的奇数次幂,复杂度玄学

注意一些边界问题,当算到 $prime_i >= y$ 的时候显然后面都是若干个素数的一次幂的影所以可以直接二分查

好像有个 $Max\sqrt{n}$ 的dp 可以去看队爷题解,本质上是相同的

一些细节看代码吧


// BEGIN CUT HERE
// END CUT HERE
#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e6+5;
using namespace std ;

int prime[N], cnt;
bool F[N];

inline LL calc(int x,LL y) {
    if(x == cnt + 1) return 1;
    if(prime[x] > y) return 1;
    if((LL)prime[x]*prime[x]>= y)  return  upper_bound(prime+1,prime+cnt+1,y)-prime-x+1;
    LL i = prime[x], ret = calc(x+1,y);
    for(;i<=y;) {
        ret = ret + calc(x+1,y/i);
        if((i*=prime[x])>y) break;;
        i *= prime[x];
    }
    return ret;
}

class HolyNumbers
{
    public:
    long long count(long long upTo, int maximalPrime)
    {
        cnt = 0; memset(F,false,sizeof F);
        memset(prime,0,sizeof prime);
        int j;
        for(int i=2;i<=maximalPrime;++i) {
            if(!F[i]) prime[++cnt] = i;
            for(j=1;prime[j]*i<=maximalPrime;++j) {
                F[prime[j]*i] = 1;
                if(i%prime[j]==0) break;
            }
        }
        LL ans = calc(1,upTo);
        return ans;
    }
 
    
// BEGIN CUT HERE
    public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
    private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const long long &Expected, const long long &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() { long long Arg0 = 10LL; int Arg1 = 100; long long Arg2 = 8LL; verify_case(0, Arg2, count(Arg0, Arg1)); }
    void test_case_1() { long long Arg0 = 10LL; int Arg1 = 3; long long Arg2 = 5LL; verify_case(1, Arg2, count(Arg0, Arg1)); }
    void test_case_2() { long long Arg0 = 123LL; int Arg1 = 12; long long Arg2 = 32LL; verify_case(2, Arg2, count(Arg0, Arg1)); }
    void test_case_3() { long long Arg0 = 123LL; int Arg1 = 456; long long Arg2 = 88LL; verify_case(3, Arg2, count(Arg0, Arg1)); }
    void test_case_4() { long long Arg0 = 123456789LL; int Arg1 = 12345; long long Arg2 = 25994500LL; verify_case(4, Arg2, count(Arg0, Arg1)); }

// END CUT HERE

};
// BEGIN CUT HERE
int main(){
    HolyNumbers ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

···
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP