SGU 537 Divisibility
乱搞+容斥。这道题可以暴力求解出所有组合情况，然后求所有情况的公因子就可以了，但是这样的话10！ * 100 会超时，我们单独考虑出现10种字母的情况。时间复杂度就会变成9！*100了，这样就可以AC了。当出现10种字母时，会有3种情况： 1. 当所以字母只出现一次时，可以暴力算出，公因子只有1， 3， 9 ，然后我们发现这种情况所得的满足情况的数，的位数和固定为45，的确会是3和9的倍数。
2. 根据第一种情况，可以推出，当一种字母出现4次，其他字母都只出现一次时，一定可以被3整除。。。然后暴力了几个样例，发现都只能被1,3整除。。。然后就厚颜易做图的这样写了。。。主啊，原谅我的无知吧。。。实在是证不出来了。。。。。
3.然后发现剩余的情况都是只有1了。。
同学YY到另一种很快的方法，那就是当使用字母小于10的时候，对于原串比如aba，则组成的情况为101*a + 10 * b。。。101和10的公因子肯定满足任意的情况，然后对于任意组合a， b 必能找到 a和b 使得 和的公因子不包含别的因子（这个也没证出来，发的题解供大家对拍吧。。。。）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 16;
const int M = 4000000;
bool isp[M];
int p[M], cnt = 0;
char ch[N];
void get_p()
{
CLR(isp, true);
isp[1] = isp[0] = 0;
for(int i = 2; i < M; i ++)
{
if(isp[i])
{
p[cnt ++] = i;
if(i < 4000)for(int j = i * i; j < M; j += i)
isp[j] = false;
}
}
return ;
}
vector<LL> hav, bef;
set<LL> ans;
set<LL>::iterator it;
int num[1000], tot;
LL 易做图(LL a, LL b)
{
return b ? 易做图(b, a % b) : a;
}
void dfs(int st, LL now)
{
ans.insert(now);
if(st >= tot) return;
LL tmp = 1;
for(int i = 0; i <= num[st]; i ++)
{
dfs(st + 1, now * tmp);
tmp *= bef[st];
}
return ;
}
void solve(LL dan)
{
bef.clear();int tmp = 0;tot = 0;
for(int i = 0; (LL)p[i] * p[i] <= dan; i ++)
{
tmp = 0;
while(dan % p[i] == 0)
{
dan /= p[i];
tmp ++;
}
if(tmp) bef.push_back(p[i]), num[tot ++] = tmp;
}
if(dan > 1) bef.push_back(dan), num[tot ++] = 1;
ans.clear();
dfs(0, 1);
for(it = ans.begin(); it != ans.end(); it ++)
{
LL tmp = *it;
printf(" %I64d", tmp);
}puts("");
}
LL sb[30];
int id[30], sid;
bool vis[11];
void dfs1(int st, LL now)
{
if(st == sid)
{
hav.push_back(now);
return;
}
for(int i = 0; i < 10; i ++)
{
if(!i && !st) continue;
if(vis[i]) continue;
vis[i] = 1;
dfs1(st + 1, now + sb[st] * (LL)i);
vis[i] = 0;
}
}
int main()
{
//freopen("in.txt", "r", stdin);
int t, len, cas = 1;LL ans;
get_p();scanf("%d", &t);
while(t --)
{
scanf("%s", ch);
len = strlen(ch);hav.clear();
CLR(sb, 0);sid = 0;CLR(id, -1);
for(int i = 0; i < len; i ++)
{
if(id[ch[i] - 'a'] < 0)
{
id[ch[i] - 'a'] = sid ++;
}
}
for(char i = 'a'; i <= 'z'; i ++)
{
LL tmp = 0;
for(int j = 0; j < len; j ++)
{
tmp *= 10;
if(i == ch[j]) tmp += 1;
}
if(tmp) sb[id[i - 'a']] = tmp;
}
printf("Case %d:", cas ++);
if(sid < 10)
{
CLR(vis, 0);
dfs1(0, 0);
ans = 0;
for(int i = 0; i < hav.size(); i ++)
ans = 易做图(ans, hav[i]);
solve(ans);
}
else
{
if(len == 10) puts(" 1 3 9");
else if(len == 13)
{
CLR(sb, 0);bool flag = 0;
for(int i = 0; i < len; i ++)
{
sb[ch[i] - 'a'] ++;
if(sb[ch[i] - 'a'] == 4) flag = 1;
}
if(flag) puts(" 1 3");
else puts(" 1");
}
else puts(" 1");
}
}
}
[cpp] view plaincopyprint?
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 16;
const int M = 4000000;
bool isp[M];
int p[M], cnt = 0;
char ch[N];
void get_p()
{
CLR(isp, true);
isp[1] = isp[0] = 0;
for(int i = 2; i < M; i ++)
{
if(isp[i])
{
p[cnt ++] = i;
if(i < 4000)for(int j = i * i; j < M; j += i)
isp[j] = false;
}
}
return ;
}
vector<LL> hav, bef;
set<LL> ans;
set<LL>::iterator it;
int num[1000], tot;
LL 易做图(LL a, LL b)
{
return b ? 易做图(b, a % b) : a;
}
void dfs(int st, LL now)
{
ans.insert(now);
if(st >= tot) return;
LL tmp = 1;
for(int i = 0; i <= num[st]; i ++)
{
dfs(st + 1, now * tmp);
tmp *= bef[st];
}
return ;
}
void solve(LL dan)
{
bef.clear();int tmp = 0;tot = 0;
for(int i = 0; (LL)p[i] * p[i] < dan; i ++)
{
tmp = 0;
while(dan % p[i] == 0)
{
dan /= p[i];
tmp ++;
}
if(tmp) bef.push_back(p[i]), num[tot ++] = tmp;
}
if(dan > 1) bef.push_back(dan), num[tot ++] = 1;
ans.clear();
dfs(0, 1);
for(it = ans.begin(); it != ans.end(); it ++)
{
LL tmp = *it;
printf(" %I64d", tmp);
}puts("");
}
int sb[30];
int main()
{
//freopen("in.txt", "r", stdin);
int t, len, cas = 1;LL ans;
get_p();scanf("%d", &t);
while(t --)
{
scanf("%s", ch);CLR(sb, 0);
printf("Case %d:", cas ++);
len = strlen(ch);hav.clear();
for(char i = 'a'; i <= 'z'; i ++)
{
LL tmp = 0;
for(int j = 0; j < len; j ++)
{
tmp *= 10;
if(ch[j] == i) tmp += 1;
}
if(tmp) hav.push_back(tmp);
}ans = 0;
if(hav.size() < 10)
{
for(int i = 0; i < hav.size(); i ++)
ans = 易做图(ans, hav[i]);
solve(ans);
}
else
{
if(len == 10) puts(" 1 3 9");
else if(len == 13)
{
CLR(sb, 0);bool flag = 0;
for(int i = 0; i < len; i ++)
{
sb[ch[i] - 'a'] ++;
if(sb[ch[i] - 'a'] == 4) flag = 1;
}
if(flag) puts(" 1 3");
else puts(" 1");
}
else puts(" 1");补充：软件开发 , C++ ,
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊