链接 点击跳转
题解 推一推式子，发现 ( i a ? j a , i b ? j b ) = ( i b ? j b , i a ? b ? j a ? b ) (i^a-j^a,i^b-j^b)=(i^b-j^b,i^{a-b}-j^{a-b}) (ia?ja,ib?jb)=(ib?jb,ia?b?ja?b)
这都证出来了，那不就结束了吗？
显然 ( i a ? j a , i b ? j b ) = i ( a , b ) ? j ( a , b ) (i^a-j^a,i^b-j^b)=i^{(a,b)}-j^{(a,b)} (ia?ja,ib?jb)=i(a,b)?j(a,b)
题目在很不起眼的地方写了 a a a和 b b b互质，所以 ( a , b ) = 1 (a,b)=1 (a,b)=1
所以这题就是求
∑ i = 1 n ∑ j = 1 i ( i ? j ) [ ( i , j ) = 1 ] \sum_{i=1}^n\sum_{j=1}^i(i-j)[(i,j)=1] i=1∑n?j=1∑i?(i?j)[(i,j)=1]
推一推就可以得到
1 2 ∑ i = 2 n i φ ( i ) \frac{1}{2}\sum_{i=2}^n i\varphi(i) 21?i=2∑n?iφ(i)
【#|hdu6706,2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛 huntian oy】杜教筛裸题
代码
#include
#define maxn 1000010
#define linf (1ll<<60)
#define iinf 0x3f3f3f3f
#define mod 1000000007ll
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;
_<=(__);
_++)
using namespace std;
typedef long long ll;
typedef pair pll;
struct EasyMath
{
ll prime[maxn], phi[maxn];
bool mark[maxn];
ll fastpow(ll a, ll b, ll c)
{
ll t(a%c), ans(1ll);
for(;
b;
b>>=1,t=t*t%c)if(b&1)ans=ans*t%c;
return ans;
}
void get_prime(ll N)
{
ll i, j;
for(i=2;
i<=N;
i++)mark[i]=false;
*prime=0;
phi[1]=1;
for(i=2;
i<=N;
i++)
{
if(!mark[i])prime[++*prime]=i, phi[i]=i-1;
for(j=1;
j<=*prime and i*prime[j]<=N;
j++)
{
mark[i*prime[j]]=true;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
}em;
ll f[1500], iphi[maxn], N, _6;
ll getf(ll x){return x>1)%mod;
}
void calc(ll n)
{
if(n>T;
em.get_prime(maxn-1);
for(i=1;
i>N>>a>>b;
cl(f);
calc(N);
ll ans=(getf(N)-1)*em.fastpow(2,mod-2,mod)%mod;
cout<<(ans+mod)%mod< 推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托，是时候捣鼓一下家中的小米电视机啦。