发布于 由itewqq

[暑期集训][数学][数论][组合数学] SPOJ Square-free integers

（其实一开始想的是错的，实际上就是mu[i]^2的前缀和S

先考虑对立面，2到n之间有多少个数可以被平方数整除？可以枚举从2到sqrt(n)，然后把可以被这些数字的平方整除的算上，也就是n/(i^2)个对于每个来说。但是这里会有重复的，比如i分别为2，3，6时，算上了4，9，36，其中36被算了两遍，所以要加加减减。（好吧其实我也还没自己证明出来但是今天有点疲回头填坑ooorz

错误的话，code length竟然超了，其他的话都是用的模板应该没什么问题emmm

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;
typedef long long LL;
const int maxn=10000010;
const int MOD=1e9+7;


int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}



int mob[maxn],vis[maxn],p[maxn];


void Mobius()
{
    int pnum = 0;
    mob[1] = 1;

    for(int i = 2; i < maxn; i++)
    {
        if(!vis[i])
        {
            p[pnum ++] = i;
            mob[i] = -1;
        }
        for(int j = 0; j < pnum && i * p[j] < maxn; j++)
        {
            //noprime[i * p[j]] = false;
            vis[i * p[j]] = 1;
            if(i % p[j] == 0)
            {
                mob[i * p[j]] = 0;
                break;
            }
            mob[i * p[j]] = -mob[i];
        }
    }
}


int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    Mobius();
    int T;
    LL n,sqn,sum;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        scanf("%lld",&n);
        sqn=sqrt(n+0.5);
        for (int i=2;i<=sqn;i++)
        {
            //cout<

 


 


 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据。