正題

---

大意

給出一個(gè)分?jǐn)?shù)ABAB求它在k進(jìn)制下的小數(shù)循環(huán)。
如果是有限小數(shù)直接輸出位數(shù)
無(wú)限循環(huán)輸出混循環(huán)節(jié)和循環(huán)節(jié)長(zhǎng)度。

---

代碼

直接切正題
用a數(shù)組表示每一位的余數(shù)，然后a[0]=Aa[0]=A，之后a[1]=a[0]?K%Ba[1]=a[0]?K%B，然后如果有q位那么a[q]=AKq%B=Aa[q]=AKq%B=A。然后我們先讓A和B互質(zhì)，然后計(jì)算混循環(huán)節(jié)就是每次B/gcd(B,k)B/gcd(B,k)讓gcd(B,k)<=1gcd(B,k)<=1的次數(shù)，如果最后B=1B=1那么就是有限小數(shù)，混循環(huán)節(jié)長(zhǎng)度就是位數(shù)。不然我們開(kāi)始計(jì)算循環(huán)節(jié)，現(xiàn)在A和B已經(jīng)經(jīng)過(guò)了前面的計(jì)算，我們用處我們剛才的式子直接計(jì)算q，AKq%B=A%BAKq%B=A%B，然后將A消去就是

Kq≡1(mod??b)Kq≡1(modb)
之后根據(jù)歐拉定理
Kφ(b)≡1(mod??b)Kφ(b)≡1(modb)
但是我們要求最小解，所以我們可以將 φ(b)φ(b)分解質(zhì)因數(shù)然后將可以的答案除去。

---

代碼

#include<cstdio> #define ll long long using namespace std; int t; ll a,b,k,d,ans1; ll gcd(ll a,ll b) {if (a%b==0) return b;return gcd(b,a%b); } ll ksm(ll x,ll k)//轉(zhuǎn)化二進(jìn)制計(jì)算x*k以免炸范圍 {ll ans=0;while(k){if (k&1) ans=(ans+x)%b;x=(x*2)%b;k>>=1;}return ans; } ll qsm(ll x,ll k)//快速冪 {ll ans=1;while(k){if (k&1) ans=ksm(ans,x);x=ksm(x,x);k>>=1;}return ans; } ll phi(ll x)//計(jì)算歐拉 {ll ans=x;for (ll i=2;i*i<=x;i++)if (x%i==0) {ans=ans/i*(i-1);while (x%i==0) x/=i;}if (x>1) ans=ans/x*(x-1);return ans; } int main() {scanf("%d",&t);b=99;printf("%d",qsm(17,30));return 0;while (t--){scanf("%lld%lld%lld",&a,&b,&k);ans1=0;ll d=gcd(a,b);a/=d;b/=d;d=gcd(b,k);while ((d=gcd(b,k))>1) b/=d,ans1++;if (b==1) {printf("%lld 0\n",ans1);continue;}//計(jì)算混循環(huán)節(jié)printf("%lld",ans1);ll x,y;x=y=phi(b);for (ll i=2;i*i<=x;i++)if (!(y%i)){while (!(x%i)&&qsm(k,x/i)==1) x/=i;//計(jì)算答案do y/=i; while(!(y%i));//分解質(zhì)因數(shù)}if (y>1&&qsm(k,x/y)==1) x/=y;//特判答案printf(" %lld\n",x);} }

總結(jié)

以上是生活随笔為你收集整理的jzoj3384-理工男【欧拉定理,gcd,数论】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。