频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 3243 大步小步算法
2014-04-03 11:20:16         来源:POJ 3243 大步小步算法  
收藏   我要投稿
Clever Y
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 6195 Accepted: 1500

Description

Little Y finds there is a very interesting formula in mathematics:

XY mod Z = K

Given X, Y, Z, we all know how to figure outK fast. However, given X, Z, K, could you figure outY fast?


Input

Input data consists of no more than 20 test cases. For each test case, there would be only one line containing 3 integersX, Z, K (0 ≤ X, Z, K ≤ 109).
Input file ends with 3 zeros separated by spaces.

Output

For each test case output one line. Write "No Solution" (without quotes) if you cannot find a feasibleY (0 ≤ Y < Z). Otherwise output the minimum Y you find.

Sample Input

5 58 33
2 4 3
0 0 0

Sample Output

9
No Solution


模板题,测试模板

代码:

/* ***********************************************
Author :rabbit
Created Time :2014/4/2 21:01:29
File Name :7.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
class HASH{  
    public:  
        struct node{  
            ll next,first,second;  
        }edge[140000];  
        ll tol,head[140100];  
        void clear(){  
            memset(head,-1,sizeof(head));  
            tol=0;  
        }  
        void add(ll x,ll y){  
            if(find(x)!=-1)return;
            ll t=x%65535;  
            edge[tol].next=head[t];  
            edge[tol].first=x;  
            edge[tol].second=y;  
            head[t]=tol++;  
        }  
        ll find(ll x){  
            ll t=x%65535;  
            for(ll i=head[t];i!=-1;i=edge[i].next)  
                if(edge[i].first==x)return edge[i].second;  
            return -1;  
        }  
}mi;  
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
	if(!b){d=a;x=1;y=0;return;}
	exgcd(b,a%b,d,y,x);y-=x*(a/b);
}

ll pow_mod(ll a,ll n,ll m){
    ll res=1;
    a%=m;
    while(n){
        if(n&1) res=res*a%m;
        a=a*a%m;
        n>>=1;
    }
    return res;
}
ll BabyStep_GiantStep(ll A,ll B,ll C){
       B%=C;
    ll tmp=1;mi.clear();
    for(int i=0;i<=100;++i){
        if(tmp==B%C) return i;
        tmp=tmp*A%C;
    }
    ll D=1,d=0;
    while((tmp=gcd(A,C))!=1){
        if(B%tmp) return -1;
        C/=tmp;
        B/=tmp;
        D=D*A/tmp%C;
        d++;
    }
    ll m=(ll)ceil(sqrt((double)C));
    tmp=1;
    for(int i=0;i<=m;++i){
        mi.add(tmp,i);
        tmp=tmp*A%C;
    }
    ll x,y,K=pow_mod(A,m,C),dd;
    for(int i=0;i<=m;++i)
    {
        exgcd(D,C,dd,x,y);
        tmp=((B*x)%C+C)%C;
        if((y=mi.find(tmp))!=-1)return i*m+y+d;
        D=D*K%C;
    }
    return -1;
}
int main(){
   ll A,B,C;
    while(cin>>A>>C>>B){
        if(!A&&!B&&!C) break;
        ll ans=BabyStep_GiantStep(A,B,C);
        if(ans==-1)cout<<"No Solution"<

点击复制链接 与好友分享!回本站首页
相关TAG标签 小步 大步 算法
上一篇:Palindrome Partitioning II -- LeetCode
下一篇:ACM-DFS之Beat——hdu2614
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站