NOIP模拟赛拓展

题目描述 Description###

$φ$ 函数是数论中非常常用的函数。对于正整数 $x$ ，$φ(x)$ 表示不超过 $x$ 的所有正整数与 $x$ 互质的个数。

现在我们对它进行一次拓展：对于正整数 $x$ ,$y$ ，定义 $φ(x,y)$ 表示不超过 $y$ 的所有正整数与 $x$ 互质的个数。

现在我们给定正整数 $n$ 和 $m$ ，对于所有不超过 $n$ 的正整数 $i$ ，求 $φ(i,m)$ 。

输入描述 Input Description###

输入仅一行两个正整数 $n$ 和 $m$ 。

输出描述 Output Description###

输出 $n$ 行，每行一个整数。第 $i$ 行表示 $φ(i,m)$ 。

样例输入 Sample Input###

11 10

样例输出 Sample Output###

数据范围及提示 Data Size & Hint###

$n \leq 10^5,m \leq 10^{15}$

之前的一些废话###

题解###

正难则反，我们考虑$m$ 以内能被$n$ 整除的所有数，含有所有$n$ 的因子的很显然是可以的，然后我们就可以通过容斥原理来加加减减来求得这个值，找找规律可以发现，含有平方因子的数不会参与其中的讨论，含有奇数个质因子的数应该是加，含有偶数个质因子的数应该是减，所以我们来一个素数筛来预处理每一个数的符号，然后$\sqrt{i} $ 的时间枚举每一个i的因数，然后进行计算。复杂度$ O(预处理+n\sqrt{n} )$

代码###

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

#define X first

#define Y second

#define mp make_pair

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

inline LL read()

{

    LL x=0,f=1;char c=getchar();

    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}

    while(isdigit(c)){x=x*10+c-'0';c=getchar();}

    return x*f;

}

const int maxn=100000;

int n,prime[maxn],end,sign[maxn+20];

LL m,sum;

bool vis[maxn+20];

void init()

{

	for(int i=2;i<=maxn;i++)

		if(!vis[i])

		{

			prime[++end]=i;

		    for(LL j=(LL)i*(LL)i;j<=(LL)maxn;j+=i)vis[j]=1;

		}

	for(int i=2;i<=maxn;i++)

	{

		if(!vis[i])sign[i]=1;

		if(!sign[i])continue;

		for(int j=1;j<=end && (LL)i*(LL)prime[j]<=maxn;j++)

		{

			if(i%prime[j]==0)sign[i*prime[j]]=0;

			else sign[i*prime[j]]=-sign[i];

		}

	}

}

int main()

{

    init();

	n=(int)read();m=read();

	printf("%lld\n",m);

	for(int i=2;i<=n;i++)

    {

    	int s=(int)sqrt(i);

    	sum=0ll;

    	for(int j=1;j<=s;j++)

    		if(i%j==0)

    		{

	    		if(j!=1)sum+=(m/j)*sign[j];

	    		if(j*j!=i)sum+=(m/(i/j))*sign[i/j];

	    	}

    	printf("%lld\n",m-sum);

    }

    return 0;

}

总结###

找找规律画画图这种题还是比较简单的。

事后发现这玩意居然是莫比乌斯函数，我居然自己推出了这么高深的东西！

巴特西

NOIP模拟赛拓展

题目描述 Description###

输入描述 Input Description###

输出描述 Output Description###

样例输入 Sample Input###

样例输出 Sample Output###

数据范围及提示 Data Size & Hint###

之前的一些废话###

题解###

代码###

总结###

最新文章

热门文章

巴特西

NOIP模拟赛 拓展

题目描述 Description###

输入描述 Input Description###

输出描述 Output Description###

样例输入 Sample Input###

样例输出 Sample Output###

数据范围及提示 Data Size & Hint###

之前的一些废话###

题解###

代码###

总结###

最新文章

热门文章

NOIP模拟赛拓展