YAPTCHA UVALive - 4382（换元+威尔逊定理）

题意就是叫你求上述那个公式在不同N下的结果。思路：很显然的将上述式子换下元另p=3k+7则有 Σ【（p-1）!+1/p-[(p-1)!/p]】接下来用到一个威尔逊定理，如果p为素数则

( p -1 )! ≡ -1 ( mod p ) 即（p-1）！+1 为 p的整数倍因此不难发现【*】里面要么为0，要么为1，为1的情况就是p为素数的情况，然后统计k=1-n中有多少个3*k+1素数就好了

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = 3e6+, INF = 0x7fffffff;

int vis[maxn], ans[maxn];

void init()

{

    mem(vis, );

    for(int i=; i<=sqrt(maxn+0.5); i++)

        if(!vis[i])

            for(int j=i*i; j<maxn; j+=i)

                vis[j] = ;

}

void f()

{

    mem(ans, );

    for(int i=; i<= 1e6; i++)

    {

        int temp = *i+;

        ans[i] = ans[i-] + ( - vis[temp]);

    }

}

int main()

{

    init();

    f();

    int T, n;

    cin>> T;

    while(T--)

    {

       cin>> n;

       cout<< ans[n] <<endl;

    }

    return ;

}

巴特西

YAPTCHA UVALive - 4382（换元+威尔逊定理）

最新文章

热门文章