自学摄影教程的网站有哪些,客户对网站建设公司的评价,深圳家具网站建设,个人网站设计模板传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
首先nnn很小的话可以暴力连边#xff0c;让后染个色求一个颜色最多的即可。但是这个题显然不行#xff0c;由于是三次方#xff0c;所以考虑质因子入手。 首先很容易就能想到将所有的数…传送门
文章目录题意思路题意 思路
首先nnn很小的话可以暴力连边让后染个色求一个颜色最多的即可。但是这个题显然不行由于是三次方所以考虑质因子入手。 首先很容易就能想到将所有的数的质因子的幂次模上333之后他对应的乘起来为三次方数的数是唯一的。因为对于同一个质数来说aaa的幂次为0,1,20,1,20,1,2对应的bbb的幂次为0,2,10,2,10,2,1所以现在问题就变成了如何快速将所有数的幂次模333并且求出来他对应的数然后答案就是二者取一个maxmaxmax即可因为二者一定是一个取一个不取即染上不同的色。下面考虑如何将所有数幂次模333。 我们可以筛出来200020002000以内的质数的三次幂让后每次遍历跑一遍即可。这样筛出来的数xxx的质因子幂次都333但是我们要求他对应的数怎么办呢显然不能直接分解质因子这样的复杂度还是(2e9)\sqrt{(2e9)}(2e9)的这里有一个巧妙的做法就是对x∗xx*xx∗x再进行一次上面的分解得出来的数即为xxx对应的数因为x∗xx*xx∗x可以将原来111变成222222变成4mod314\bmod 314mod31正符合上面的规律。 复杂度约为O(n∗200)O(n*200)O(n∗200)。
// Problem: 牛牛的最大兴趣组
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/7604/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int a[N];
LL prime[N],cnt;
mapLL,intmp,has;
bool st[N];void get_prime(int n) {for(int i2;in;i) {if(!st[i]) {prime[cnt]1ll*i*i*i;for(int jii;jn;ji)st[j]true;}}
}LL divide(LL x) {for(int i1;icnt;i) {if(x%prime[i]0) {while(x%prime[i]0) x/prime[i];}if(prime[i]x) return x;}return x;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);get_prime(1300);coutcntendl;scanf(%d,n);for(int i1;in;i) {scanf(%d,a[i]);a[i]divide(a[i]);mp[a[i]];has[a[i]]divide(1ll*a[i]*a[i]);}int ans0;for(auto x:mp) {if(x.X1) {ans;continue;}LL fahas[x.X];ansmax(mp[fa],x.Y);x.Y0; mp[fa]0;}coutansendl;return 0;
}
/**/
