网站备案填写,房地产平面设计网站,皮皮果网站建设,营销型网站的建设要求都有什么除了最后一题都比较简单就写一起了 P4450-双亲数
题目链接:https://www.luogu.com.cn/problem/P4450
题目大意
给出A,B,dA,B,dA,B,d求有多少对(a,b)(a,b)(a,b)满足gcd(a,b)dgcd(a,b)dgcd(a,b)d且a∈[1,A],b∈[1,B]a\in[1,A],b\in[1,B]a∈[1,A],b∈[1,B]
解题思路
很显然的…除了最后一题都比较简单就写一起了 P4450-双亲数
题目链接:https://www.luogu.com.cn/problem/P4450
题目大意
给出A,B,dA,B,dA,B,d求有多少对(a,b)(a,b)(a,b)满足gcd(a,b)dgcd(a,b)dgcd(a,b)d且a∈[1,A],b∈[1,B]a\in[1,A],b\in[1,B]a∈[1,A],b∈[1,B]
解题思路
很显然的容斥枚举ddd的倍数iii然后容斥系数就是μ(id)\mu(\frac{i}{d})μ(di)。 时间复杂度O(n)O(n)O(n)
code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e610;
int A,B,d,mu[N],pri[N],cnt;
long long ans;
bool v[N];
int main()
{scanf(%d%d%d,A,B,d);mu[1]1;for(int i2;iN;i){if(!v[i])pri[cnt]i,mu[i]-1;for(int j1;jcnti*pri[j]N;j){v[i*pri[j]]1;if(i%pri[j]0)break;mu[i*pri[j]]-mu[i];}}if(AB)swap(A,B);for(int id;iA;id)ans1ll*(A/i)*(B/i)*mu[i/d];printf(%lld\n,ans);
}P5221-Product
题目链接:https://www.luogu.com.cn/problem/P5221
题目大意
给出nnn求 ∏i1n∏j1nlcm(i,j)gcd(i,j)\prod_{i1}^n\prod_{j1}^n\frac{lcm(i,j)}{gcd(i,j)}i1∏nj1∏ngcd(i,j)lcm(i,j)
解题思路
CYJian\text{CYJian}CYJian的题啊时限0.2s?0.2s?0.2s?不过只是看起来花里胡哨没有其他CYJian\text{CYJian}CYJian的题那么难。
先简单把lcmlcmlcm拆出来化一下式子 (∏i1n∏j1ni×j)1(∏i1n∏j1ngcd(i,j))2\left(\prod_{i1}^n\prod_{j1}^ni\times j\right)\frac{1}{\left(\prod_{i1}^{n}\prod_{j1}^ngcd(i,j)\right)^2}(i1∏nj1∏ni×j)(∏i1n∏j1ngcd(i,j))21
左边那个很容易求就是(n!)2n(n!)^{2n}(n!)2n右边那个因为是乘积所以很好做直接枚举质数幂ded^ede让有⌊nde⌋2\lfloor\frac{n}{d^e}\rfloor^2⌊den⌋2对数的gcdgcdgcd包含ded^ede会产生这么多的贡献但是因为在de−1d^{e-1}de−1的时候也统计过一次所以只需要产生ddd的贡献就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn)
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,P104857601;
ll n,ans,cnt,pri[N];
bool v[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{scanf(%lld,n);ans1;for(ll i2;in;i){if(!v[i]){for(ll ji;jn;jj*i)ansans*power(i,(n/j)*(n/j)%(P-1))%P;pri[cnt]i;}for(ll j1;jcnti*pri[j]n;j){v[i*pri[j]]1;if(i%pri[j]0)break;}}anspower(ans*ans%P,P-2);ll f1;for(ll i1;in;i)ff*i%P;fpower(f,2*n);ansans*f%P;printf(%lld,ans);return 0;
}P6055-[RC-02]GCD
题目链接:https://www.luogu.com.cn/problem/P6055
题目大意
给出nnn求 ∑i1n∑j1n∑p1⌊nj⌋∑q1⌊nj⌋[gcd(i,j)1][gcd(p,q)1]\sum_{i1}^n\sum_{j1}^n\sum_{p1}^{\lfloor\frac{n}{j}\rfloor}\sum_{q1}^{\lfloor\frac{n}{j}\rfloor}[gcd(i,j)1][gcd(p,q)1]i1∑nj1∑np1∑⌊jn⌋q1∑⌊jn⌋[gcd(i,j)1][gcd(p,q)1]
解题思路
刚开始还以为可以直接暴力整除分块杜教筛欧拉函数然后O(n34)O(n^{\frac{3}{4}})O(n43)搞然后发现时限是1s1s1s。
发现这个式子的顺序很奇怪特意的把jjj放在了里面。这个提示我们jjj其实是在枚举ppp和qqq的gcdgcdgcd。 而又jjj和iii互质其实这个式子的真正目的是对于每个iii求有多少对数的gcdgcdgcd和iii互质然后求和。换成式子就是 ∑i1n∑q1n∑p1n[gcd(gcd(q,p),i)1]\sum_{i1}^n\sum_{q1}^n\sum_{p1}^n[gcd(gcd(q,p),i)1]i1∑nq1∑np1∑n[gcd(gcd(q,p),i)1] 就是三对数之间互质的对数之间上莫反就可以了 ∑i1n⌊ni⌋3μ(i)\sum_{i1}^n\lfloor\frac{n}{i}\rfloor^3\mu(i)i1∑n⌊in⌋3μ(i) nnn比较大要用杜教筛筛一下mumumu
时间复杂度O(n23)O(n^{\frac{2}{3}})O(n32) code
#includecstdio
#includecstring
#includealgorithm
#includemap
#define ll long long
using namespace std;
const ll N1e710,P998244353;
ll n,cnt,pri[N],mu[N],ans;
mapll,ll mp;
bool v[N];
ll get_sum(ll n){if(mp.find(n)!mp.end())return mp[n];if(nN)return mu[n];ll rest1;for(ll l2,r;ln;lr1)rn/(n/l),(restP-(r-l1)*get_sum(n/l))%P;return mp[n]rest;
}
signed main()
{scanf(%lld,n);mu[1]1;for(ll i2;iN;i){if(!v[i])pri[cnt]i,mu[i]-1;for(ll j1;jcnti*pri[j]N;j){v[i*pri[j]]1;if(i%pri[j]0)break;mu[i*pri[j]]-mu[i];}}for(ll i1;iN;i)(mu[i]mu[i-1])%P;for(ll l1,r;ln;lr1){rn/(n/l);ll pn/l;pp*p%P*p%P;(ansp*(get_sum(r)-get_sum(l-1))%P)%P;}printf(%lld\n,(ansP)%P);return 0;
}