2020联赛训练3
T1
//60分做法 我们发现对于这个式子它其实可以理解为对于每个(a mod i)都乘上(b mod i)的加和 与 (b mod i)都乘上 (a mod i)的加和 的和,这样其实也就是求出sum(a mod i) * sum(b mod i) 但是题目要求 i = j时不能加,所以再做容斥原理即可。 时间复杂度 O(n) //100分做法 //划重点 这题需要用到一个叫/*数论分块*/的东西,不做详细说明,证明和详解我觉得这个比较好 //https://www.cnblogs.com/luckyblock/p/12614236.html 于是的话呢对于suma 和 sumb也不做详解,CQOI2007余数求和就是搞这个的(自己luogu,那么我们的容斥原理 部分展开后就是 res = min(a,b) * a % mod * b % mod; res = res - (b * (a / i) % mod * sum(i,j) % mod) - (a * (b / i) % mod * sum(i,j) % mod) + ((a / i) * (b / i) % mod * (SUM(j) - SUM(i - 1)) % mod); //分割线 这题考场上真的懵了,数论题做得比较少,还需练习qwq code:#include<cstdio> #include<iostream> #define ll long long using namespace std; const ll mod = 1e9 + 7; ll inv2,inv6,a,b; ll getr(ll x,ll n) { return n / (n / x); } ll getinv(ll x,ll y) { ll res = 1; while(y > 0) { if(y % 2)res = res * x % mod; y >>= 1; x = x * x % mod; } return res; } ll sum(ll l,ll r) { return (l + r) * (r - l + 1) % mod * inv2 % mod; } ll SUM(ll n) { return (n + 1) * n % mod * (2 * n + 1) % mod * inv6 % mod; } int main() { inv2 = getinv(2,mod-2); inv6 = getinv(6,mod-2); scanf("%lld%lld",&a,&b); ll res,suma,sumb; res = suma = sumb = 0; for(ll i = 1,j = 0;i <= a;i += 1) { j = getr(i,a); suma += ((a * (j - i + 1) % mod - (a / i) * sum(i,j) % mod) % mod); suma %= mod; i = j; } if(suma < 0)suma += mod; for(ll i = 1,j = 0;i <= b;i += 1) { j = getr(i,b); sumb += ((b * (j - i + 1) % mod - (b / i) * sum(i,j) % mod) % mod); sumb %= mod; i = j; } if(sumb < 0)sumb += mod; res = min(a,b) * a % mod * b % mod; for(ll i = 1,j,p,q;i <= min(a,b);i += 1) { p = getr(i,a); q = getr(i,b); j = min(p,q); res = res - (b * (a / i) % mod * sum(i,j) % mod) - (a * (b / i) % mod * sum(i,j) % mod) + ((a / i) * (b / i) % mod * (SUM(j) - SUM(i - 1)) % mod); res = (res + mod) % mod; i = j; } if(res < 0)res += mod; printf("%lld\n",((((suma + mod) % mod * (sumb + mod) % mod + mod) % mod - res) + mod) % mod); return 0; }
T2
首先化简题意,u的值:若分解质因数总个数为奇数就是-1否则1,若存在平方数是自己的因 数 那就是0。 对于这个东西我们不难用线性筛求出。 关键是怎么去模拟剩下w = w + u[w]的过程 我们发现每四个连续数一定有4是它们其中一个的因数,也就是说到这个点它就不动了!那我 们的最大周期就是4,那周期中有没有更小的循环周期呢?是有的!如果u_lastw = -1而现在 u_w = 1显然也是循环。 所以。。。。 懂了吧 //分割线 当时考场心态炸裂毕竟读不懂题。。。以后还是有自信的,要不然又 100-> 30了 code: #include<cstdio> #include<iostream> #include<map> using namespace std; const int MAXN = 1e7 + 17; int t,maxn,n[MAXN];long long k[MAXN]; int prime[MAXN],v[MAXN],u[MAXN],m,num[MAXN]; bool vis[MAXN]; int main() { cin >> t; for(int i = 1;i <= t;i += 1) scanf("%d%lld",&n[i],&k[i]); for(int i = 2;i <= 1e7;i += 1) { if(v[i] == 0) { m++; prime[m] = i; u[i] = -1; } for(int j = 1;j <= m && prime[j] * i <= 1e7;j += 1) { v[prime[j] * i] = 1; if(i % prime[j] == 0) { u[i * prime[j]] = 0; break; } u[prime[j] * i] = -u[i]; } } u[1] = 1; int tex = 0; for(int i = 1;i <= t;i += 1) { tex = 0; int w = n[i]; for(int j = 1;j <= k[i];j += 1) { int lastw = w; w = w + u[w]; if(u[lastw] == -1 && u[w] == 1) { tex = 1; if((k[i] - j) % 2)printf("%d\n",lastw); else printf("%d\n",w); break; } if(!u[w]) { tex = 1; printf("%d\n",w);break; } } if(!tex)printf("%d\n",w); } return 0; }
T3
还没写无哇哇哇哇我好菜啊!!