Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1995 Raising Modulo Numbers---数论

Posted on 2010-02-06 04:05 Uriel 阅读(377) 评论(0)  编辑 收藏 引用 所属分类: POJ数学
        直接用快速模取幂的模板过的。。还记得是09' Regional 上海赛热身赛的某题数论知道式子不用快速模取幂就一直TLE。。然后从天哥大牛那里第一次知道了这个东西。。这题是第一次在POJ上用到。。
/*Problem: 1995  User: Uriel 
   Memory: 164K  Time: 94MS 
   Language: C++  Result: Accepted
*/
 

#include
<stdio.h>
#include
<stdlib.h>

int a,b,t,m,res,h;

int modExp(int a, int b, int n)
{
    
int t = 1, y = a;
    
while(b != 0)
    
{
        y 
%= n;
        
if(b % 2 == 1)
            t 
= t % n * y % n;
        y 
= y * y % n; 
        b 
= b >> 1;
    }

    
return t;
}


int main()
{
    
int i;
    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%d",&m);
        scanf(
"%d",&h);
        res
=0;
        
for(i=0;i<h;i++)
        
{
            scanf(
"%d %d",&a,&b);
            res
=(res+modExp(a,b,m))%m;
        }

        printf(
"%d\n",res);
    }

//    system("PAUSE");
    return 0;
}

            

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理