[暑期集训][数学][数论][组合数学] 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来减少垃圾评论。了解我们如何处理您的评论数据