姗姗来迟力
居然没有第一时间写 laffey 酱的题,真的是大不敬,呜呜呜。
看到题面的第一眼就觉得是个嘎嘎难的数论,毕竟是 laffey 的题,然后试着搞了个人类智慧的暴力。
相信大家都知道费马小定理,不知道的可以看 laffey 的题解,这里不再列出。实际上是不会写公式
设左边的式子结果是 ,右边的式子结果是 ,当 的时候就符合了费马小定理了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unsigned int c=451*4;
ll fast(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)
ans=ans*a%c;
a=a*a%c;
b>>=1;
}
return ans;
}
ll n,ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
ll a=(fast(i,11)-fast(i,4))*(fast(i,11)-i);
ll b=(fast(i,11)-i)*(fast(i,451)-fast(i,4));
if(b==0)
{
if(a==0)
{
cout<<i<<endl;
ans++;
}
continue;
}
if(b%a!=0)
continue;
for(int j=1;j<=3;j++)
{
if(a>b)
break;
if(a==b)
{
cout<<i<<endl;
ans++;
break;
}
a*=a;
}
}
cout<<ans;
return 0;
}
遍历到 纯属人类智慧,因为一开始写的 之后慢慢往下调整的,虽然都是 分没变。
之后去问了问 laffey 酱可不可打表,他告诉我可以,因为这道题是有规律的。
我就打了一个小小的表,发现 到 全是符合题目要求的,然后就这样输入一个 再输出 就 AC 掉了。
共 1 条回复
tql