首页 > 代码库 > 序列变换
序列变换
yk有两序列a和b。
lyk想知道存在多少对x,y，满足以下两个条件。
1：gcd(x,y)=1。
2： abx = bay 。
例如若a={1,1,1}，b={1,1,1}。那么存在7对，因为除了x=2,y=2或x=3,y=3外都满足条件。
Input
第一行一个数n(1<=n<=100000)。接下来一行n个数，表示ai(1<=ai<=n)。接下来一行n个数，表示bi(1<=bi<=n)。
Output
一行表示答案
Input示例
31 1 11 1 1
Output示例
7
思路：莫比乌斯反演
F（n）表示gcd是i的倍数的有多少对，然后根据莫比乌斯反演求出f（1）;
1 #include<bits/stdc++.h> 2 typedef long long LL; 3 using namespace std; 4 bool prime[100005]; 5 LL ak[100005]; 6 LL mul[100005]; 7 LL cnt[100005]; 8 int a[100005]; 9 int b[100005];10 const int BufferSize=1<<16;11 char buffer[BufferSize],*head,*tail;12 inline char Getchar() {13 if(head==tail) {14 int l=fread(buffer,1,BufferSize,stdin);15 tail=(head=buffer)+l;16 }17 return *head++;18 }19 inline int read() {20 int x=0,f=1;char c=Getchar();21 for(;!isdigit(c);c=Getchar()) if(c==‘-‘) f=-1;22 for(;isdigit(c);c=Getchar()) x=x*10+c-‘0‘;23 return x*f;24 }25 int main(void)26 {27 int cn = 0;28 mul[1] = 1;29 for(int i = 2; i <= 100000; i++)30 {31 if(!prime[i])32 {33 ak[cn++] = i;34 mul[i] = -1;35 }36 for(int j = 0; j < cn&&(LL)ak[j]*i<=100000; j++)37 {38 if(i%ak[j])39 {40 prime[i*ak[j]] = true;41 mul[i*ak[j]] = -mul[i];42 }43 else44 {45 prime[i*ak[j]] = true;46 mul[i*ak[j]] = 0;47 break;48 }49 }50 }51 int n;52 scanf("%d",&n);53 for(int i = 1; i <= n; i++)54 a[i] = read();55 for(int i = 1; i <= n;i++)56 b[i] =read();57 LL sum = 0;58 for(int i = 1; i <= n; i++)59 {60 if(mul[i])61 {62 for(int j = i; j <= n; j+=i)63 cnt[a[b[j]]]++;64 for(int j = i; j <= n; j+=i)65 sum=sum+mul[i]*(cnt[b[a[j]]]);66 for(int j = i; j <= n; j+=i)67 cnt[a[b[j]]]--;68 }69 }70 printf("%lld\n",sum);71 return 0;72 }
序列变换
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。