题意:有一个字符串,要求使用其中字符构造一个环(不必全部都用),定义一个环是k美的,如果它转\(k\)次仍是原样,现在给你\(k\),要求最长的k美环的长度.

题解:我们首先看\(k\),如果一个环转\(k\)的因子次是美的,那么\(k\)次也一定是美的,然后再看环,假如一个环最少转\(d\)次是美的,那么这个环的长度\(n\)一定能被\(d\)整除.也就是这个环有\(d\)种不同的数,每种数有\(n/d\)个.其实也就可以把看作是一个循环节构成的,画一画也就知道了.

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

int t;
int n,k;
string s;
map<char,int> mp;
vector<int> v;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
	cin>>t;
	 while(t--){
	 	mp.clear();
	 	v.clear();
	 	cin>>n>>k;
	 	cin>>s;
	 	for(int i=0;i<n;++i){
	 		mp[s[i]]++;
	 	}
	 	for(int i=1;i<=k;++i){
	 		if(k%i==0){
	 			v.pb(i);
	 		}
	 	}
	 	int ans=0;
	 	for(int i=1;i<=n;++i){
	 		for(auto w:v){
	 			if(w%i==0){
	 				ans=max(ans,i);    //worst situation
	 			}
	 			if(i%w==0){
	 				int d=i/w;
	 				int cnt=0;
	 				for(char j='a';j<='z';++j){
	 					cnt+=mp[j]/d;
	 				}
	 				if(cnt>=w){
	 					ans=max(ans,i);
	 				}
	 			}
	 		}
	 	}
	 	cout<<ans<<endl;
	 	
	 }

    return 0;
}