JZOJ5868. 【NOIP2018模拟9.13】寻梦

题目大意

给出n,k，询问n是否可以用k的约数家和的形式表示。

题解

很显然，只有k的质因子是有用的，
分类讨论，
如果只有一个质因子，那么就直接取模。
如果只有两个质因子，那么就扩展欧几里得。
如果超过三个质因子，那么最小的一个质因子就一定小于$10^5$105，只有就可以用最短路来解决。

code

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <time.h>
#define ll long long
#define N 31622777
#define M 1000003
#define db double
#define P putchar
#define G getchar
#define inf 998244353
#define pi 3.1415926535897932384626433832795
using namespace std;
char ch;
void read(ll &n)
{
	n=0;
	ch=G();
	while((ch<'0' || ch>'9') && ch!='-')ch=G();
	ll w=1;
	if(ch=='-')w=-1,ch=G();
	while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
	n*=w;
}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

ll n,m,k,a[103],w[103],T,num,ss[N],id;
bool bz[N],bz_[M];
ll f[M],v[103],b[103];
int q[N+M*10],head,tail,x;
bool ans[M];

struct node
{
	ll n,k,id;
}tt[M];

bool cmp(node a,node b)
{
	return a.k<b.k;
}

void pre()
{
    memset(bz,1,sizeof(bz));
    for(int i=2;i<N;i++)
    {
        if(bz[i])ss[++ss[0]]=i;
        for(int j=1;j<=ss[0] && ss[j]*i<N;j++)
        {
            bz[i*ss[j]]=0;
            if(i%ss[j]==0)break;
        }
    }
}

ll gcd(ll x,ll y){return x%y?gcd(y,x%y):y;}

ll exgcd(ll a,ll b,ll& x,ll& y)
{
    if(b==0)
    {
        x=1;y=0;return a;
    }
    else
    {
        ll d=exgcd(b,a%b,y,x);
        y=y-a/b*x;
        return d;
    }
}

void work_1(int id)
{
	ans[id]=(n%a[1]==0 && a[1]!=1);
}

void work_2(int id)
{
	ll x,y;
	exgcd(a[2],a[1],x,y);
	x=((ll)x*(n%a[1])%a[1]+a[1])%a[1];
	y=((ll)n-(ll)x*a[2])/a[1];
	ans[id]=(x>=0 && y>=0);
}

void solve(int id)
{
	memset(a,0,sizeof(a));
	for(int i=1;ss[i]*ss[i]<=k;i++)
		if(k%ss[i]==0)
		{
			a[++a[0]]=ss[i];
			for(;k%ss[i]==0;k=k/ss[i]);
		}
	if(k>1)a[++a[0]]=k;
	if(a[0]==0)a[0]=a[1]=1;
}

void work_3(int id)
{
	int nn=a[0],t;
	ll p=a[1],w;
	for(int i=2;i<=nn;i++)
		b[i]=a[i]%p,v[i]=a[i]/p;
	memset(f,127,sizeof(f));
    memset(bz_,1,sizeof(bz_));
    for(head=M,q[tail=1+M]=f[0]=bz_[0]=0;head<tail;)
    {
        x=q[++head];
        for(int i=2;i<=nn;i++)
        {
            t=x+b[i];w=f[x]+v[i];
            if(t>=p)w++,t=t-p;
            if(f[t]>w)
            {
                f[t]=w;
                if(bz_[t])
				{
					bz_[t]=0;
					if(f[t]<f[q[head+1]])q[head--]=t;else q[++tail]=t;
				}
            }
        }
        bz_[x]=1;
    }
}

int main()
{
	pre();
	freopen("fantasy.in","r",stdin);
	freopen("fantasy.out","w",stdout);

	read(num);m=0;read(T);
	for(int i=1;i<=T;i++)
		read(tt[i].n),read(tt[i].k),tt[i].id=i;
	
	sort(tt+1,tt+1+T,cmp);
	
	for(int i=1;i<=T;i++)
	{
		n=tt[i].n;k=tt[i].k;
		if(tt[i].k!=tt[i-1].k)solve(id),work_3(tt[i].id);
		if(a[0]==1)work_1(tt[i].id);else
		if(a[0]==2)work_2(tt[i].id);else
    		ans[tt[i].id]=(f[n%a[1]]<=n/a[1]);
	}
	
	for(int i=1;i<=T;i++)
	{
    	if(ans[i])P('Y'),P('E'),P('S');
			else P('N'),P('O');
		P('\n');
	}
	return 0;
}