admin管理员组文章数量:1606762
492. Goblin's Appreciation
时间限制 1000 ms 内存限制 65536 KB题目描述
Your clan has been subjected to the harassment of the goblins. Your leader decided to fight back for peace. But the story is more complex than your imagination, reckoning with the numerous resources wasted in the war, the leader assigned you as the envoy to win the dignity.
Now you have arrived there, you find the goblins love math very much. They only appreciate the guys with high intellegence, so they give you a math problem, if you can solve it in 1s, they will appreciate you and protect your clan as a gift. For peace, just fighting!
They give you a lot of pairs of numbers, denoted by K,N. for every input, you should tell them the sum of k^gcd(i,n), for i = 1~n.
For the answer is so large, you can give them the answer mod 23333.
输入格式
Given T, the number of cases. Then, for next T lines, there are two numbers K,N.(1 <= k <= 10^4, 1 <= n <= 10^8)
输出格式
For every case, print one line, containing the answer mod 23333.
输入样例
3
3 4
2 6
100 50000000
输出样例
96
84
3014
这道题过得太艰辛,当时比赛的时候就想到暴力一定不行,要用欧拉来算,但是没有想到还是超时,今天在大神的各种指导下终于做出来了。
有几个点备注一下提醒自己:
pow太慢而且返回的是double类型。
头文件: math.h/ cmath( C++中) 功能:计算x的y次 幂。 返回值:x不能为负数且y为小数,或者x为0且y小于等于0,返回幂指数的结果。 返回类型: double型,int,float会给与警告!要写快速幂。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;//longlong
const int mod=23333;
const int maxn=100000008;
int n;
int ephi(int n) //欧拉函数,求的是小于n的质因数的个数,这个ephi(n/i)的结果即i为最大公因数的个数。
{
int res=n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
res=res/i*(i-1);
for(;n%i==0;n/=i) ;
}
}
if(n!=1)
res=res/n*(n-1);
return res;
}
long long mod_pow(long long x,long long n,int mod) //快速幂,同时取模了。
{
long long res=1;
while (n>0)
{
if(n&1) res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
long long ans=0;
int e;
long long n,k;
scanf("%lld%lld",&k,&n);
for(int i=1;i*i<=n;i++) // 注意终止条件,只枚举到sqrt(n),在后面判断。
{
if(n%i==0) //找n的因数
{
e=ephi(n/i);
ans+=e*mod_pow(k,i,mod);
if(n/i!=i) //这个地方是关键,由于i是n的因数则n/i也一定是n的因数,可知只要枚举到sqrt即可,然后若因数不重复,则对应地进行一次操作。
{ e=ephi(n/(n/i));
ans+=e*mod_pow(k,n/i,mod);
}
}
}
printf("%lld\n",ans%mod);
}
return 0;
}
本文标签: 排位赛暑假新生AppreciationGoblin
版权声明:本文标题:2014新生暑假个人排位赛final---492. Goblin's Appreciation 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728512016a1161644.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论