首页 > > 程序设计 > C/C++ >

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

2018-06-17 21:44:04来源：未知阅读 ()

方法就是枚举，根据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掉了...真的分解质因数（要打质数表）还是要记一下。

  1 %:pragma GCC optimize(2)
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<map>
  6 #include<set>
  7 using namespace std;
  8 typedef int LL;
  9 LL prime[10000];
 10 bool vis[50100];
 11 LL ans0[24],ans1[24];
 12 map<LL,LL> ma;
 13 map<LL,LL>::iterator it;
 14 set<LL>::iterator it2;
 15 set<LL> se;
 16 LL temp[2][2000];
 17 LL size,anss;
 18 LL a0,a1,b0,b1,T;
 19 LL gcd(LL a,LL b)
 20 {
 21     LL t;
 22     while(b!=0)
 23     {
 24         t=a;
 25         a=b;
 26         b=t%b;
 27     }
 28     return a;
 29 }
 30 LL pow2(LL x,LL y)
 31 {
 32     LL base=x,ans=1;
 33     while(y>0)
 34     {
 35         if(y&1)    ans*=base;
 36         base*=base;
 37         y>>=1;
 38     }
 39     return ans;
 40 }
 41 void dprime(LL n,LL ans[])
 42 {
 43     LL i;
 44     LL end=floor(sqrt(n+0.5));
 45     for(i=1;prime[i]<=end;i++)
 46         while(n!=prime[i])
 47         {
 48             if(n%prime[i]==0)
 49             {
 50                 if(ma.count(prime[i])==0)
 51                     ma[prime[i]]=++size;
 52                 ans[ma[prime[i]]]++;
 53                 n/=prime[i];
 54             }
 55             else
 56                 break;
 57         }
 58     if(ma.count(n)==0)
 59         ma[n]=++size;
 60     ans[ma[n]]++;
 61 }
 62 int main()
 63 {
 64     
 65     LL ii,i,j,d,dd,d1,d2;
 66     for(i=2;i<=50000;i++)
 67     {
 68         if(!vis[i])    prime[++prime[0]]=i;
 69         for(j=1;j<=prime[0]&&i*prime[j]<=50000;j++)
 70         {
 71             vis[i*prime[j]]=1;
 72             if(i%prime[j]==0)    break;
 73         }
 74     }
 75     scanf("%d",&T);
 76     while(T--)
 77     {
 78         memset(ans0,0,sizeof(ans0));
 79         memset(ans1,0,sizeof(ans1));
 80         se.clear();anss=0;
 81         ma.clear();size=0;
 82         scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
 83         dprime(b0,ans0);
 84         dprime(b1,ans1);
 85         if(ma.count(1)==1)    ans0[ma[1]]=1,ans1[ma[1]]=1;
 86         ii=0;
 87         memset(temp[0],0,sizeof(temp[0]));
 88         temp[0][0]=1;
 89         temp[0][1]=1;
 90         for(it=ma.begin();it!=ma.end();it++)
 91         {
 92             ii^=1;
 93             memset(temp[ii],0,sizeof(temp[ii]));
 94             d=it->second;
 95             dd=it->first;
 96             d1=ans0[d];
 97             d2=ans1[d];
 98             if(d1>d2)
 99             {
100                 puts("0");
101                 goto xxx;
102             }
103             else if(d1==d2)
104             {
105                 for(i=1;i<=temp[ii^1][0];i++)
106                     for(j=0;j<=d2;j++)
107                         temp[ii][++temp[ii][0]]=temp[ii^1][i]*pow2(dd,j);
108             }
109             else
110             {
111                 for(i=1;i<=temp[ii^1][0];i++)
112                     temp[ii][++temp[ii][0]]=temp[ii^1][i]*pow2(dd,d2);
113             }
114         }
115         for(i=1;i<=temp[ii][0];i++)
116             se.insert(temp[ii][i]);
117         for(it2=se.begin();it2!=se.end();it2++)
118         {
119             if(gcd(*it2,a0)==a1)
120                 anss++;
121         }
122         printf("%d\n",anss);
123         xxx:;
124     }
125     return 0;
126 }

假的分解质因数：

void dprime(int n,int ans[])
{
    int i;
    for(i=2;i<=n;i++)
        while(n!=i)
        {
            if(n%i==0)
            {
                if(ma.count(i)==0)
                    ma[i]=++size;
                ans[ma[i]]++;
                n/=i;
            }
            else
                break;
        }
    if(ma.count(n)==0)
        ma[n]=++size;
    ans[ma[n]]++;
}