给定两个正整数a,b，分别定义两个集合L和R，
集合L：即把1~a，1~b中整数乘积的集合定义为L = {x * y | x,y是整数且1 <= x <=a , 1 <= y <= b}；
集合R：1~a，1~b中整数异或的集合定义为集合R = {x ^ y | x,y是整数且1 <= x <=a , 1 <= y <= b}，其中^表示异或运算。
现从L中任取一个整数作为A，从R中任取一个整数作为B，如果必要在B的左边补0，使得B达到：“b的位数+1”位（十进制），然后把B接到A的右边，形成的一个十进制数AB。求所有这样形成数的和。
输入a,b 1<=a<=30, 1<=b<=10000000。
输出所有产生的AB数的和，由于结果比较大，输出对1000000007取余数的结果。
例如：a = 2, b = 4，
则L = {1 * 1, 1 * 2, 1 * 3, 1 * 4, 2 * 1, 2 * 2, 2 * 3, 2 * 4} = {1, 2, 3, 4, 6, 8}
R = {1^1,1^2,1^3,1^4,2^1,2^2,2^3,2^4} = {0, 1, 2, 3, 5, 6}
相接的时候保证R中的数至少有两位，所以相接后所有的AB数的集合是
{
100, 101, 102, 103, 105, 106,
200, 201, 202, 203, 205, 206,
300, 301, 302, 303, 305, 306,
400, 401, 402, 403, 405, 406,
600, 601, 602, 603, 605, 606,
800, 801, 802, 803, 805, 806
}
输出它们的和：14502。
假设b的位数为kb, 集合L，R中所有元素的和分别为sumL、sumR，集合L，R中元素的个数分别为sizeL、sizeR。从题目所给的例子可以很容易的分析出最后的结果 = sumL * (10^(kb + 1)) * sizeR + sumR * sizeL （对1000000007求模）。所以我们的目标是求sumL、sizeL和sumR、sizeR。
一 求集合R：sumR、sizeR
我们假设a <= b (如果a > b 可以两者交换)，a的十进制位数为ka, b的十进制位数为kb。因此异或求解集合R中元素时，只有b的最后ka个二进制位受影响，b的前kb-ka个二进制位可以表示0…2^(kb-ka)-1的所有数。现在我们只考虑b的后面ka个二进制位：
1、假设b = 11001，a = 101，那么R = {00001…11001}^{001…101}表示的数有哪些呢？ 我们可以看到两者异或后可以表示的最大的数是11001^100 = 11101（注意到后三位异或能表示的最大为001^100 = 101）, 最小的数是00001^001 = 00000（注意到后三位异或能表示的最小为001^001 = 000），界于最大和最小的数之间的所有数都可以表示（这是因为后三位异或可以表示000~101之间的所有数）。
2、假设b = 11000，a = 101，那么R = {00001…11001}^{001…101}表示的数有哪些呢？ 我们可以看到两者异或后可以表示的最大的数是11001^100 = 11101（注意到后三位异或能表示的最大为001^100 = 101）, 最小的数是00001^001 = 00000（注意到后三位异或能表示的最小为001^001 = 000），界于最大和最小的数之间的所有数都是不是都可以表示呢，答案是否定的，b本身就不能表示(11000 = 11000^000, 但是题目中说明了y>=1,y不能等于0)。
3、那么什么时候R中不包括b呢：当b的后ka个二进制位全部为0时，b就不属于集合R
4、如何R中的最大元素，要求最大元素，就要使b的后ka个二进制位中1的个数最多，假设a = 10110101， b的后8位为backb = 00101101，注意到我们可以通过异或使backb从左边第三位(左起第一个1)起全部为1(即101101^010010 = 111111)，backb的前两位最大能表示00^10 = 10，因此a^backb最大为10111111。即选取b的后ka个二进制位backb，把backb左起第一个二进制位1开始全部置1，backb的其余为和a的对应位异或，这样得到的数就是R的最大值。
5、还需要注意一点是，如果a、b中有一个数为1，那么R中1就不属于集合R，因为1要和0异或才能得到1.
综上所述，我们可以根据步骤4求得R的最大值，那么R = {0，1,2…maxR}，然后根据步骤3和步骤5判断一下b和1是否要从R中剔除，求R的复杂度为O(32)（32为整数的位数）
二 求集合L：sumL，sizeL
最简单的就是枚举，用哈希表排除重复元素，但是这样时间复杂度为O(ab), 当b很大时，会超时。
注意到其实我们没有必要求出L中所有的元素，我们需要的是L中元素的个数和元素的和。同理假设a <= b
sumL =
1*{1,2,3…b} +
2*{1,2,3…b} +
…+
a*{1,2,3…b} - 重复的元素
假设集合Li = i * {1,2,3…b}, 注意到为避免重复元素，对于i，不用每次都从1开始乘, 至少可以从 i 开始即 Li = i *{i, i+1,…b}。我们还可以进一步缩小范围，假设i 素因子分解后 i = m * n * k，其中k是最小的素因子，那么我只要从max( b / k +1, i )开始乘，因为m*n*k*(b/k + 1) = m*n*b + i. 当i = m*n 时，m*n*b前面已经计算过，因此至少可以从m*n*b + i 开始计算。所以Li = i * {j, j+1, … ,b}, 其中j = max( b / minPrimeFactor(i) + 1, i ) （ i = 1 时特别考虑）。
所以sumL = U( Li )， 其中（i = 1…a, U表示求集合的并集）。
求集合的并集，我们很容易想到容斥原理：
那么对于集合Lj …Lk的交集可以如下求：
先求j, j+1, …, k 的最小公倍数lcm，那么他们的交集 = lcm * {start…end}, 其中
start = ceil（max( max(b / minPrimeFactor(i) + 1, i ) ) / lcm），i = j…k （即交集的最小元素 >= 所有集合的第一个元素的最大值）
end = j*b / lcm （即交集的最大元素 <= 第一个集合的最大元素）
如果a = 30我们就要求2^30-1次交集，注意到求交集的过程中很多为空集，比如L1∩L2 = 空集，因此L1∩L2∩L3就没必要求了，这样可以减去很多计算。可以通过dfs搜索+剪枝来求sumL，求的过程中我们也很容易求得sizeL。本文地址
三 求最终结果
通过公示 sumL * (10^(kb + 1)) * sizeR + sumR * sizeL （对1000000007求模）求最终结果
最后还需要注意的是，由于数据较大，用int会溢出，（我求最小公倍数时用int，这个错误找了好久）
class Test {
private:
static const long long MAXRES = 1000000007;
static int round(double d)
{
return ceil(d) - d < d - floor(d) ? ceil(d) : floor(d);
}
static long long sequenceSum(int minVal, int maxVal)
{
if(minVal > maxVal)return 0;
return (minVal + maxVal)*(maxVal - minVal + 1LL)/2;
}
//compute Least Common Multiple of a,b
static long long lcm(long long a, long long b)
{
long long tmp, aCopy = a, bCopy = b;
while(b != 0)
{
tmp = b;
b = a % b;
a = tmp;
}
//a is gcd(a,b)
return aCopy / a * bCopy;
}
//compute sum(R) and sizeof(R)
static void computeR()
{
bitset<32> bitMin(minp),bitMax(maxp);
int i = 31;
for(; i >= 0; i--)//find the first bit '1' in minp
if(bitMin[i] == true)break;
int minpBitNum = i + 1;
//containMax indicates whether element max(a,b) is in set R
bool containMax = false;
for(int k = 0; k < minpBitNum; k++)
if(bitMax[k] == true)containMax = true;
for(; i >= 0 && bitMax[i] == false; i--)
bitMax[i] = bitMax[i]^bitMin[i];
for(; i >= 0; i--)
bitMax[i] = true;
int maxR = bitMax.to_ulong();//max element in set R
sumR = 0;//sum of elements in R
sizeR = maxR + 1;//the number of element in R
sumR = sequenceSum(1, maxR);
if(!containMax)
{
sumR = (sumR - maxp) % MAXRES;
if(sumR < 0)sumR += MAXRES;
sizeR--;
}
if(minp == 1)
{
sumR--;
sizeR--;
}
}
static bool computeLRecur(int index, vector<int> &vec, long long lcmVec)
{
if(index == minp + 1)
{
int vecSize = vec.size();
if(vecSize == 0)return true;
int op = vecSize%2 == 0 ? -1 : 1;
int seqStart = 0;
for(int i = 0; i < vecSize; i++)
seqStart = max(seqStart, mulStartVal[vec[i]]);
seqStart = ceil( seqStart * 1.0 / lcmVec );
int seqEnd = vec[0] * maxp / lcmVec;
if(seqStart <= seqEnd)
{
sumL = (sumL + op * lcmVec *sequenceSum(seqStart, seqEnd))
% MAXRES ;
sizeL += op * (seqEnd - seqStart + 1);
return true;
}
else
return false;
}
if(computeLRecur(index + 1, vec, lcmVec))
{
vec.push_back(index);
computeLRecur(index + 1, vec, lcm(lcmVec, index));
vec.pop_back();
return true;
}
else return false;
}
//compute sum(L) and sizeof(L)
static void computeL()
{
//min prime factor of [0,1,2...30]
int minPriFac[] = {0, 1,2,3,2,5,2,7,2,3,2, 11,2,13,2,3,2,17,2,19,2
,3,2,23,2,5,2,3,2,29,2};
sumL = 0;
sizeL = 0;
mulStartVal.clear();
mulStartVal.push_back(0);
mulStartVal.push_back(1);
for(int i = 2; i <= minp; i++)
mulStartVal.push_back(max(maxp / minPriFac[i] + 1, i) * i);
vector<int> vec;
computeLRecur(1, vec, 1);
}
public:
static int minp, maxp;//minp = min(a,b),maxp = max(a,b)
//sumR = sum of elelment in set R
//sumL = sum of elelment in set L
//sizeR = number of element in set R
//sizeL = number of element in set L
static long long sumR, sizeR, sizeL, sumL;
static vector<int> mulStartVal;
static int run (int a,int b)
{
//--------compute the digit number of b
int bDigitNum = 0;
for(int bcopy = b, factor = 10; bcopy != 0;)
{
bcopy = bcopy / factor;
bDigitNum++;
}
minp = a > b ? b : a;
maxp = a > b ? a : b;
//--------comput sum(R) and sizeof(R)
computeR();
//--------comput sum(L) and sizeof(L)
computeL();
//compute final result, result = sumL*factor*sizeR + sumR*sizeL
long long factor = round(pow(10.0, bDigitNum + 1));
long long res = sumL * factor % MAXRES;
res = res * sizeR % MAXRES;
res = (res + (sizeL * sumR)) % MAXRES;
return res;
}
};
int Test::minp;
int Test::maxp;
long long Test::sumL;
long long Test::sizeL;
long long Test::sizeR;
long long Test::sumR;
vector<int> Test::mulStartVal;
//------------------------------------------
int main()
{
int a = 30, b = 10000000;
cout<<Test::run(a,b)<<endl;
return 0;
}
顺便附上caopengcs大神的代码，感谢他的分享
const int M = ; int NUM,SUM;
int num[],sum[],all[]; class Test3 {
public:
static int length(int x) {
int i;
for (i = ; x; x /=, ++i)
;
return i;
} static long long gcd(long long x,long long y) {
return y?gcd(y, x % y):x;
} static int mul(long long x, long long y) {
if (x >= M) {
x %= M;
}
if (y >= M) {
y %= M;
}
if( (x *= y) >= M) {
x %= M;
}
return x;
} static int add(long long x,long long y) {
if (x >= M) {
x %= M;
}
if (y >= M) {
y %= M;
} if ((x += y) >= M) {
x -= M;
}
return (int) x;
} static int dec(long long x,long long y) {
if (x >= M) {
x %= M;
}
if (y >= M) {
y %= M;
}
if ((x -= y) < ) {
x += M;
}
return (int) x;
} static void help(long long x, int one,int *a,int now,int len, long long lcm) { if (now >= len) {
if (one == ) {
return;
}
long long n = x / lcm;
int s;
if (n & ) {
s = mul(n, (n + ) >> );
}
else {
s = mul(n >> , n + );
}
s = mul(s, lcm);
if (one & ) {
SUM = add(SUM, s);
NUM = add(NUM, n);
}
else {
SUM = dec(SUM, s);
NUM = dec(NUM, n);
}
return;
}
help(x, one, a, now + , len, lcm);
long long temp = a[now] / gcd(lcm, a[now]);
if (temp > x / lcm) {
return;
}
lcm *= temp;
help(x, one + , a, now + , len, lcm);
} static int run(int a,int b) {
int lenb = length(b), lena = length(a), len, L = ;
memset(num,,sizeof(num));
memset(sum,,sizeof(sum));
for (int i = ; i <= a; ++i) {
if ((i != ) && ((i ^ ) <= b)) {
num[] = add(num[], );
sum[] = add(sum[], );
break;
}
}
if (b > ) {
for (int i = ; i <= a; ++i) {
if ((i != b) && ((i ^ b) <= b)) {
num[] = add(num[], );
sum[] = add(sum[], b);
break;
}
}
}
for (int i = ; i < b; ++i) {
num[] = add(num[], );
sum[] = add(sum[], i);
}
num[] = add(num[], ); //
for (int i = ; i <= a; ++i) {
for (int j = ; j <= a; ++j) {
if ((((i + b) ^ j) <= b) && (i + b != j)) {
len = max(length(i + b) - lenb - , );
num[len] = add(num[len], );
sum[len] = add(sum[len], i + b);
L = max(L, len);
break;
}
}
} int s = , n = ;
// ( (i - 1) * B, i * B]
int m = ;
for (int i = a; i; --i) {
int k = ;
for (int j = ; j < m; ++j) {
if (all[j] % i) {
all[k++] = all[j];
}
}
all[k++] = i;
m = k;
long long x = ((long long) i) * ((long long) b);
SUM = NUM = ;
help(x, , all, , m, );
s = add(s, SUM);
n = add(n, NUM);
SUM = NUM = ;
help(x - b, , all, , m, );
s = dec(s, SUM);
n = dec(n, NUM);
}
int w = ;
for (int i = ; i <= lenb; ++i) {
w = mul(w, );
}
int answer = ;
int numR = ; for (int i = ; i <= L; ++i) {
//printf("%d %d\n",num[i], sum[i]); answer = add(add(mul(mul(s, w), num[i]), mul(n, sum[i])), answer);
numR += num[i];
}
//cout<<"L: "<<s<<" "<<n<<endl;
//cout<<"R: "<<numR<<endl;
return answer;
}
};
【版权声明】转载请注明出处：http://www.cnblogs.com/TenosDoIt/p/3496453.html