NOIP2012同余方程

描述

求关于 x的同余方程  ax ≡ 1(mod b) 的最小正整数解。

输入格式

输入文件 mod.in
输入只有一行，包含两个正整数a,b,用一个空格隔开。

输出格式

输出文件 为 modmod .out 。
输出只有一行,包含一个正整数，包含一个正整数 ，包含一个正整数 x0，即最小正整数解。 输入据保证一定有解。

测试样例1

输入

输出

备注

对于 40% 的数据    2 ≤b≤1,000
对于 60% 的数据    2 ≤b≤50,000,000
对于 100%的数据    2 ≤a, b≤2,000,000,000NOIP2012-TG

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

using namespace std;

ll euler_phi(ll x){

    ll m = (ll)sqrt(x+0.5);

    ll ans = x;

    for(int i = ;i <= m;i++){

        if(x % i == ){

            ans = ans / i * (i-);

            while(x % i == ) x /=  i;

        }

    }

    if(x > ) ans = ans / x * (x-);

    return ans;

}

ll q_mul(ll a,ll b,ll p){

    ll ans = ;

    while(b){

        if(b&){

            ans = (ans + a) % p;

            b--;

        }

        b >>= ;

        a = (a + a) % p;

    }

    return ans;

}

ll q_pow(ll a,ll b,ll p){

    ll ans = ;

    while(b){

        if(b&){

            ans = q_mul(ans,a,p);

        }

        b >>= ;

        a = q_mul(a,a,p);

    }

    return ans;

}

void exgcd(ll a,ll b,ll& d,ll& x,ll& y){

    if(b == ){

        x = ;

        y = ;

        d = a;

        return;

    }

    exgcd(b,a%b,d,y,x);

    y -= (a/b)*x;

}

int phi[];

void phi_table(int n){

    for(int i = ;i <= n;i++) phi[i] = ;

    phi[] = ;

    for(int i = ;i <= n;i++) if(!phi[i])

    for(int j = i;j <= n;j+=i){

        if(!phi[j]) phi[j] = j;

        phi[j] = phi[j] / i * (i-);

    }

}

int main(){

    ll a,b,d,x,y;

    cin>>a>>b;

    cout<<q_pow(a,euler_phi(b)-,b);

    return ;

}