生活随笔
收集整理的這篇文章主要介紹了
nowcoder 牛牛的最大兴趣组 质因子 + 思维
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
傳送門
文章目錄
題意：
思路：
首先nnn很小的話可以暴力連邊，讓后染個色求一個顏色最多的即可。但是這個題顯然不行，由于是三次方，所以考慮質因子入手。
首先很容易就能想到將所有的數的質因子的冪次模上333，之后他對應的乘起來為三次方數的數是唯一的。因為對于同一個質數來說，aaa的冪次為0,1,20,1,20,1,2對應的bbb的冪次為0,2,10,2,10,2,1，所以現在問題就變成了如何快速將所有數的冪次模333，并且求出來他對應的數，然后答案就是二者取一個maxmaxmax即可，因為二者一定是一個取一個不取，即染上不同的色。下面考慮如何將所有數冪次模333。
我們可以篩出來200020002000以內的質數的三次冪，讓后每次遍歷跑一遍即可。這樣篩出來的數xxx的質因子冪次都<3<3<3，但是我們要求他對應的數怎么辦呢？顯然不能直接分解質因子，這樣的復雜度還是(2e9)\sqrt{(2e9)}(2e9)?的，這里有一個巧妙的做法，就是對x?xx*xx?x再進行一次上面的分解，得出來的數即為xxx對應的數，因為x?xx*xx?x可以將原來111變成222，222變成4mod3=14\bmod 3=14mod3=1，正符合上面的規律。
復雜度約為O(n?200)O(n*200)O(n?200)。
#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
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int a
[N
];
LL prime
[N
],cnt
;
map
<LL
,int>mp
,has
;
bool st
[N
];void get_prime(int n
) {for(int i
=2;i
<=n
;i
++) {if(!st
[i
]) {prime
[++cnt
]=1ll*i
*i
*i
;for(int j
=i
+i
;j
<=n
;j
+=i
)st
[j
]=true;}}
}LL
divide(LL x
) {for(int i
=1;i
<=cnt
;i
++) {if(x
%prime
[i
]==0) {while(x
%prime
[i
]==0) x
/=prime
[i
];}if(prime
[i
]>x
) return x
;}return x
;
}int main()
{
get_prime(1300);cout
<<cnt
<<endl
;scanf("%d",&n
);for(int i
=1;i
<=n
;i
++) {scanf("%d",&a
[i
]);a
[i
]=divide(a
[i
]);mp
[a
[i
]]++;has
[a
[i
]]=divide(1ll*a
[i
]*a
[i
]);}int ans
=0;for(auto &x
:mp
) {if(x
.X
==1) {ans
++;continue;}LL fa
=has
[x
.X
];ans
+=max(mp
[fa
],x
.Y
);x
.Y
=0; mp
[fa
]=0;}cout
<<ans
<<endl
;return 0;
}
總結
以上是生活随笔為你收集整理的nowcoder 牛牛的最大兴趣组 质因子 + 思维的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
