poj3696 快速幂的优化+欧拉函数+gcd的优化+互质

时间：2021-04-04 05:17:04

这题满满的黑科技orz

题意：给出L，要求求出最小的全部由8组成的数(eg: 8,88,888,8888,88888,.......)，且这个数是L的倍数

 

 

sol：全部由8组成的数可以这样表示：((10^x)-1)*(8/9)

那么有m=((10^x)-1)*(8/9)=k*L，answer即满足条件的最小的x

 

性质1：若ax=by且a和b互质，那么说明a中没有任何b的质因子，b的质因子一定都在x里。所以x是b的倍数。

所以先想方设法在等式中构造两个互质的数以便化简。我们取p=8/gcd(8,L)，q=9*L/gcd(8,L)

那么有p*((10^x)-1)=q*k，且p与q互质【8/gcd(8,L)与L/gcd(8,L)一定互质。8又没有3这个质因子，所以9*L/gcd(8,L)还是会互质】

所以由性质1，(10^x)-1是q的倍数。

所以(10^x)-1=0　　(mod q)

　　(10^x)=1　　（mod q)

性质2：欧拉定理。对于正整数a,n，若gcd(a,q)=1，则有a^phi(q)=1　　(mod q)　　　　【其中phi是欧拉函数】

这个式子是不是和上面很像呢~

所以若gcd(10,q)=1说明有解，否则无解

对于有解的情况，x=phi(q)就是一个解，但不一定是最小解。actually，0---phi(q)中还可能存在解。

性质3：因为后面有mod n，而余数都是有循环节的。（即一个循环周期的长度，设为r）

eg：如果有10^a=1  (mod q)，那么10^(a+r)=1  (mod q)

首先x=0是一个解【10^0=1  (mod q)】。而且已经确定phi(q)也是一个解了。所以phi(q)一定是这个循环节r的倍数。

根据性质3，r肯定也是一个解。而且是最小的。

所以只要枚举phi(q)的约数，找出其中最小的满足条件的即可。

 

 

 

-----------------------接下来是满满的黑科技orz----------------------

Q1：本题数据很大，求gcd的过程会TLE肿么办

A1：因为gcd里面有一个数字是固定的，所以可以用一下黑科技

        //q=9*N/gcd(8,N);
        q=9*N;
        for (int i=0;i<3;i++)
            if (q%2==0)
                q=q/2;
            else break;
要求的是q/gcd(8,N)
而8分解质因数之后是2^3，也就是说带8的gcd里面最多也只可能有3个2。所以直接把这3个2能除掉的都除掉就行了

 

        //if (gcd(10,q)!=1)    ans=0;
        if  ((q%2==0)||(q%5==0))
            ans=0;
10的质因子只有2和5。如果q是2或5的倍数，就说明q和10不互质。

 

 

Q2：求快速幂取模(10^x)%q的时候，数据超了long long的范围，会出错

A2：这样：

 

LL func(LL a,LL b,LL c)     //a*b%c
{
    long long ret = 0;
    while (b)
    {
        if (b & 1)
            ret = (ret + a) % c;
        a = 2 * a % c;
        b >>= 1;
    }
    return ret;
}

LL pow_mod(LL a,LL b,LL MOD)
{
    if (a==1)   return 1;
    LL t=a%MOD,ans=1;
    while(b)
    {
        if (b&1)
            ans=func(ans,t,MOD);
        t=func(t,t,MOD);
        b>>=1;
    }
    return ans;
}

 

其实我也没看懂func是个什么鬼。。。。【逃

 

 

 

AC Code：

poj3696 快速幂的优化+欧拉函数+gcd的优化+互质poj3696 快速幂的优化+欧拉函数+gcd的优化+互质
  1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 #define LL long long
  5 #define MAXL 1000
  6 
  7 LL TC=0;
  8 LL N,MOD,TM,q,ans;
  9 int phi[MAXL+5];
 10 
 11 int gcd(int a,int b)                   //辗转相除法，返回gcd(a,b)
 12 {
 13     if (b==0) return a;
 14     return gcd(b,a%b);
 15 }
 16 
 17 long long euler(long long n)
 18 {
 19     long long ret = n;
 20     for (long long i = 2; i * i <= n; i++)
 21         if (n % i == 0)
 22         {
 23             ret = ret / i * (i - 1);
 24             while (n % i == 0)
 25                 n /= i;
 26         }
 27     if (n > 1)
 28         ret = ret / n * (n - 1);
 29     return ret;
 30 }
 31 
 32 
 33 /*
 34 LL pow_mod(LL a,LL b,LL MOD)
 35 {
 36     if (a==1)   return 1;
 37     LL t=a%MOD,ans=1;
 38     while(b)
 39     {
 40         if (b&1)
 41             ans=ans*t%MOD;
 42         t=t*t%MOD;
 43         b>>=1;
 44     }
 45     return ans;
 46 }
 47 */
 48 
 49 LL func(LL a,LL b,LL c)     //a*b%c
 50 {
 51     long long ret = 0;
 52     while (b)
 53     {
 54         if (b & 1)
 55             ret = (ret + a) % c;
 56         a = 2 * a % c;
 57         b >>= 1;
 58     }
 59     return ret;
 60 }
 61 
 62 LL pow_mod(LL a,LL b,LL MOD)
 63 {
 64     if (a==1)   return 1;
 65     LL t=a%MOD,ans=1;
 66     while(b)
 67     {
 68         if (b&1)
 69             ans=func(ans,t,MOD);
 70         t=func(t,t,MOD);
 71         b>>=1;
 72     }
 73     return ans;
 74 }
 75 
 76 int main()
 77 {
 78     //calc_phi(MAXL);
 79     while (~scanf("%I64d",&N))
 80     {
 81         TC++;
 82         if (N==0)   break;
 83         //q=9*N/gcd(8,N);
 84         q=9*N;
 85         for (int i=0;i<3;i++)
 86             if (q%2==0)
 87                 q=q/2;
 88             else break;
 89 
 90         TM=euler(q);    //tm=phi[q];
 91         ans=TM;
 92         //if (gcd(10,q)!=1)
 93         if  ((q%2==0)||(q%5==0))
 94             ans=0;
 95         else
 96         {
 97             for (LL i=1; i*i<=TM; i++)
 98                 if (TM%i==0)
 99                 {
100                     LL t1=i,t2=TM/i;
101                     LL M1=pow_mod(10,t1,q);
102                     LL M2=pow_mod(10,t2,q);
103                     //cout<<t1<<" "<<M1<<endl<<t2<<" "<<M2<<endl;
104                     if ((M1==1)&&(t1<ans))
105                         ans=t1;
106                     if ((M2==1)&&(t2<ans))
107                         ans=t2;
108                 }
109         }
110         printf("Case %d: ",TC);
111         cout<<ans<<endl;
112     }
113 }
114 
115 
116 
117 /*
118 LL len,tmp,N;
119 int TC=0;
120 bool ok;
121 
122 int main()
123 {
124     while(~scanf("%I64d",&N))
125     {
126         TC++;
127         if (N==0)   break;
128         tmp=8;
129         len=1;
130         ok=false;
131         if (tmp%N==0)   ok=true;
132         while ((!ok)&&(len<=MAXL))
133         {
134             tmp=tmp*10+8;
135             len++;
136             if (tmp%N==0)
137                 ok=true;
138         }
139         if (ok)
140             printf("Case %d: %I64d\n",TC,len);
141         else
142             printf("Case %d: 0\n",TC);
143     }
144 
145     return 0;
146 }
147 */
View Code

 

Reference:

http://www.cnblogs.com/rainydays/archive/2012/11/05/2754760.html

http://blog.csdn.net/yhrun/article/details/6908470

 

标签：

相关文章