傳送門
題意： 定義相鄰數為lcm(x,y)gcd(x,y)\frac{lcm(x,y)}{gcd(x,y)}gcd(x,y)lcm(x,y)?是一個平方數，則xxx和yyy是相鄰的。現在給出q個詢問，每次詢問一個iii，表示詢問第iii秒后max1<=i<=ndimax_{1<=i<=n}d_imax1<=i<=n?di?，did_idi?表示與aia_iai?為相鄰數的個數。注意每一秒數組都會改變成與aia_iai?是相鄰數的乘積。
思路： 先考慮怎么化簡lcm(x,y)gcd(x,y)\frac{lcm(x,y)}{gcd(x,y)}gcd(x,y)lcm(x,y)?，我們知道lcm(x,y)=x?ygcd(x,y)lcm(x,y)=\frac{x*y}{gcd(x,y)}lcm(x,y)=gcd(x,y)x?y?，帶入得x?ygcd(x,y)2\frac{x*y}{gcd(x,y)^2}gcd(x,y)2x?y?，繼續化簡(x?ygcd(x,y))2(\frac{\sqrt{x*y}}{gcd(x,y)})^2(gcd(x,y)x?y??)2，所以我們可以知道如果兩個數是相鄰的，那么他們乘積一定是完全平方數。我們需要知道完全平方數有什么特點，顯然他們的質因子的冪數都是偶數，那么兩個數相乘為平方數需要滿足什么條件呢？也比較容易想到他們的質因子冪數相加為偶數，那么我們如果在乘之前就把他們的質因子的冪數模2，得到兩個新的數，這兩個新數必須相等的時候乘起來才能是平方數。那么這就比較顯然了，我們可以用mp[i]mp[i]mp[i]表示iii出現的次數，第0秒的時候只需要取一個maxmaxmax即可。考慮第零秒到第二秒什么變了，什么沒變。我們下面把相等的數的集合稱為一個團，且以下的數的質因子冪數默認是模2意義下的。 如果一個團的數量為偶數，那么把他們乘起來之后，他們的質因數的冪數都為偶數，就變成1了。如果一個團的數量為奇數，乘起來之后的質因數的冪數仍為奇數。讓后特殊處理下1的情況就好啦。可以發現從第1秒之后他們的數量不會變，只需要先得到第零秒的，再得到偶數變乘1的數量，讓后加上原來1的數量，與第零秒取maxmaxmax即可。
讓后分解質因子肯定不能n\sqrt{n}n?分解，這里可以記一下每個數的最小質因數，讓后lognlognlogn分解即可。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=2000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int prime
[N
],cnt
;
int com
[N
];
bool st
[N
];
map
<int,int>mp
;void get_prime(int n
)
{for(int i
=2;i
<=n
;i
++){if(!st
[i
]) prime
[cnt
++]=i
,com
[i
]=i
;for(int j
=0;prime
[j
]<=n
/i
;j
++){st
[prime
[j
]*i
]=true;com
[prime
[j
]*i
]=min(com
[prime
[j
]*i
],prime
[j
]);if(i
%prime
[j
]==0) break;}}
}void divide(int x
)
{map
<int,int>has
;while(x
!=1){has
[com
[x
]]++;x
/=com
[x
];}int ans
=1;for(auto x
:has
) if(x
.Y
%2==1) ans
*=x
.X
;mp
[ans
]++;
}int main()
{
memset(com
,0x3f,sizeof(com
));get_prime(1000000);int _
; scanf("%d",&_
);while(_
--){scanf("%d",&n
); mp
.clear();for(int i
=1;i
<=n
;i
++){int x
; scanf("%d",&x
);divide(x
);}int ans1
,ans2
; ans1
=ans2
=0;for(auto x
:mp
){ans1
=max(ans1
,x
.Y
);if(x
.X
==1) ans2
+=x
.Y
;else if(x
.Y
%2==0) ans2
+=x
.Y
;}int q
; scanf("%d",&q
);while(q
--){LL op
; scanf("%lld",&op
);if(op
==0) printf("%d\n",ans1
);else printf("%d\n",max(ans1
,ans2
));}}return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #694 (Div. 2) D. Strange Definition 质因子分解 + 平方数的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
