并不对劲的bzoj4652:loj2085:uoj221:p1587:[NOI2016]循环之美

题目大意

对于已知的十进制数\(n\)和\(m\)，在\(k\)进制下，有多少个数值上互不相等的纯循环小数，可以用\(x/y\)表示,其中 \(1\leq x\leq n,1\leq y\leq m\) (\(n,m\leq10^9,k\leq2000\))

题解

这个人（点这里）讲得很清楚\(\color{white}{\text{shing太强了}}\)

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define pii pair<int,int>

#define mp make_pair

#define fi first

#define se second

#define maxn 2500010

#define lim 2500000

#define maxl 2010

#define LL long long

using namespace std;

int read()

{

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)&&ch!='-')ch=getchar();

	if(ch=='-')f=-1,ch=getchar();

	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return x*f;

}

void write(LL x)

{

	if(x==0){putchar('0'),putchar('\n');return;}

	int f=0;char ch[20];

	if(x<0)putchar('-'),x=-x;

	while(x)ch[++f]=x%10+'0',x/=10;

	while(f)putchar(ch[f--]);

	putchar('\n');

	return;

}

int n,m,k,p[maxn],cnt,numk[100],num,f[maxn],no[maxn];

LL mu[maxn],ans;

map<int,LL>M;

map<pii,LL>G;

int gcd(int x,int y){if(x>y)swap(x,y);if(!x)return y;return gcd(y%x,x);}

LL getm(int x)

{

	if(x<=lim)return mu[x];

	if(M[x])return M[x];

	LL res=1;

	for(int l=2,r=0;l<=x;l=r+1)r=x/(x/l),res-=(LL)(r-l+1)*(LL)getm(x/l);

	M[x]=res;

	return res;

}

LL g(int x,int y)

{

	if(!x)return getm(y);

	if(y<=1)return y;

	if(G[mp(x,y)])return G[mp(x,y)];

	return G[mp(x,y)]=g(x-1,y)+g(x,y/numk[x]);

}

int main()

{

	n=read(),m=read(),k=read();

	no[1]=mu[1]=1;

	rep(i,1,lim)

	{

		if(!no[i])mu[i]=-1,p[++cnt]=i;

		for(int j=1;j<=cnt&&p[j]*i<=lim;j++)

		{

			no[p[j]*i]=1;

			if(i%p[j]==0){mu[i*p[j]]=0;break;}

			else mu[i*p[j]]=-mu[i];

		}

	}

	rep(i,2,lim)mu[i]+=mu[i-1];

	rep(i,1,k)f[i]=f[i-1]+(gcd(i,k)==1?1:0);

	for(int i=1;p[i]<=k;i++)if(k%p[i]==0)numk[++num]=p[i];

	for(int l=1,r=0;l<=min(n,m);l=r+1)r=min(n/(n/l),m/(m/l)),ans+=(LL)(g(num,r)-g(num,l-1))*(LL)(n/l)*(LL)(f[(m/l)%k]+(LL)((m/l)/k)*(LL)f[k]);

	write(ans);

	return 0;

}

巴特西

并不对劲的bzoj4652:loj2085:uoj221:p1587:[NOI2016]循环之美

题目大意

题解

代码

最新文章

热门文章