洛谷 P1072 Hankson 的趣味题 || 打质数表的分解质因数

方法就是枚举，根据b0和b1可以大大减小枚举范围，方法类似这个http://blog.csdn.net/hehe_54321/article/details/76021615

将b0和b1都分解质因数。记b0的某一质因数x的指数为a，b1中x的指数为b。如果a>b，那么显然对于这组b0和b1不可能有答案；如果a=b，那么ans中的x的指数可以为0到a的任意一个数；如果a<b，那么ans中x的指数只能为b。

举例：

$$
\begin{array}{l|l}
b0=37 & b1=1776 \\
\hline
37 & =37^1*3^0*2^0 \\
ans & =37^x*3^1*2^4 \\
1776 & =37^1*3^1*2^4 \\
\hline
b0=37&b1=1776 \\
96 & =3^1*2^5 \\
ans & =3^2*2^y\\
288 & =3^2*2^5
\end{array}
$$

x表示0-1的任何数，y表示0-5的任何数。这样子就可以得出所有可能的ans，然后再验证其与a0的gcd是否是a1即可。

注意：

1.像我这样写，需要特判1，因为对1分解质因数会得到1，对其他数分解都不会出现这个1。

2.曾经写了假的分解质因数，结果T掉了...真的分解质因数（要打质数表）还是要记一下。

 %:pragma GCC optimize()

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<map>

 #include<set>

 using namespace std;

 typedef int LL;

 LL prime[];

 bool vis[];

 LL ans0[],ans1[];

 map<LL,LL> ma;

 map<LL,LL>::iterator it;

 set<LL>::iterator it2;

 set<LL> se;

 LL temp[][];

 LL size,anss;

 LL a0,a1,b0,b1,T;

 LL gcd(LL a,LL b)

 {

     LL t;

     while(b!=)

     {

         t=a;

         a=b;

         b=t%b;

     }

     return a;

 }

 LL pow2(LL x,LL y)

 {

     LL base=x,ans=;

     while(y>)

     {

         if(y&)    ans*=base;

         base*=base;

         y>>=;

     }

     return ans;

 }

 void dprime(LL n,LL ans[])

 {

     LL i;

     LL end=floor(sqrt(n+0.5));

     for(i=;prime[i]<=end;i++)

         while(n!=prime[i])

         {

             if(n%prime[i]==)

             {

                 if(ma.count(prime[i])==)

                     ma[prime[i]]=++size;

                 ans[ma[prime[i]]]++;

                 n/=prime[i];

             }

             else

                 break;

         }

     if(ma.count(n)==)

         ma[n]=++size;

     ans[ma[n]]++;

 }

 int main()

 {

     LL ii,i,j,d,dd,d1,d2;

     for(i=;i<=;i++)

     {

         if(!vis[i])    prime[++prime[]]=i;

         for(j=;j<=prime[]&&i*prime[j]<=;j++)

         {

             vis[i*prime[j]]=;

             if(i%prime[j]==)    break;

         }

     }

     scanf("%d",&T);

     while(T--)

     {

         memset(ans0,,sizeof(ans0));

         memset(ans1,,sizeof(ans1));

         se.clear();anss=;

         ma.clear();size=;

         scanf("%d%d%d%d",&a0,&a1,&b0,&b1);

         dprime(b0,ans0);

         dprime(b1,ans1);

         if(ma.count()==)    ans0[ma[]]=,ans1[ma[]]=;

         ii=;

         memset(temp[],,sizeof(temp[]));

         temp[][]=;

         temp[][]=;

         for(it=ma.begin();it!=ma.end();it++)

         {

             ii^=;

             memset(temp[ii],,sizeof(temp[ii]));

             d=it->second;

             dd=it->first;

             d1=ans0[d];

             d2=ans1[d];

             if(d1>d2)

             {

                 puts("");

                 goto xxx;

             }

             else if(d1==d2)

             {

                 for(i=;i<=temp[ii^][];i++)

                     for(j=;j<=d2;j++)

                         temp[ii][++temp[ii][]]=temp[ii^][i]*pow2(dd,j);

             }

             else

             {

                 for(i=;i<=temp[ii^][];i++)

                     temp[ii][++temp[ii][]]=temp[ii^][i]*pow2(dd,d2);

             }

         }

         for(i=;i<=temp[ii][];i++)

             se.insert(temp[ii][i]);

         for(it2=se.begin();it2!=se.end();it2++)

         {

             if(gcd(*it2,a0)==a1)

                 anss++;

         }

         printf("%d\n",anss);

         xxx:;

     }

     return ;

 }

假的分解质因数：

void dprime(int n,int ans[])

{

    int i;

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

        while(n!=i)

        {

            if(n%i==)

            {

                if(ma.count(i)==)

                    ma[i]=++size;

                ans[ma[i]]++;

                n/=i;

            }

            else

                break;

        }

    if(ma.count(n)==)

        ma[n]=++size;

    ans[ma[n]]++;

}

额外的方法：

设x=a1*a2;a0=a1*a3;x*b2=b1;b0*b3=b1;

则a1*a2*b2=b1

又a1是x和a0的最大公约数，所以a2和a3互质。

又b1是x和b0的最小公倍数，所以b2和b3互质。

所以a2和a0/a1,b2和b1/b0互质。

因为a1*a2*b2=b1

所以a2*b2=b1/a1

因此a2，b2是b1/a1的因子，只需枚举并且判断是否与a3，b3互质即可。

https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1072

巴特西

洛谷 P1072 Hankson 的趣味题 || 打质数表的分解质因数

最新文章

热门文章