【数学技巧】divisor

没考虑重复lcm处理被卡TLE没A真是可惜

题目大意

$n$为$k-可表达的$当且仅当数$n$能被表示成$n$的$k$个因子之和，其中$k$个因子允许相等。

求$[A,B]$之间$k-可表达$的数的个数

$T \le 5*10^4，2 \le K \le 7，1 \le A \le B \le 10^{18}$

题目分析

每一种拆分可以视作$1=\frac{1}{a}+\frac{1}{b}+...$的形式。因为K相当小，可以先搜出每个$K$下的拆分情况，问题就转化成了求$[l,r]$之间有多少数至少是其中一个的倍数——这是一个相当经典的问题。

但是这题的数据范围要求进一步细节优化。

注意到在极限数据$K=7，T=5*10^4$下，纯粹地$2^{因数}$枚举每一种情况lcm的做法相当低效。通过观察/经验会发现，这$2^{因数}$个lcm有大量是重复的。那么我们就转而保存每个lcm的系数而非把lcm全部存下来。

这是一个计算倍数容斥问题时，显著而不甚易想起的优化。

代码很丑。没心情重构。

 #include<bits/stdc++.h>

 const int ass5[] = {, , , , , , };

 const int ass6[] = {, , , , , , };

 const int ass7[] = {, , , , , , , , , , , , , , , };

 typedef long long ll;

 int T;

 ll l,r,k,gmpAss5[],gmpAss6[],gmpAss7[];

 ll read()

 {

     char ch = getchar();

     ll num = , fl = ;

     for (; !isdigit(ch); ch = getchar())

         if (ch=='-') fl = -;

     for (; isdigit(ch); ch = getchar())

         num = (num<<)+(num<<)+ch-;

     return num*fl;

 }

 int gcd(int a, int b){return !b?a:gcd(b, a%b);}

 ll assp5(ll x)

 {

     ll ret = ;

     for (int i=; i<; i++)

         ret += x/gmpAss5[i];

     return ret;

 }

 ll assp6(ll x)

 {

     ll ret = ;

     for (int i=; i<; i++)

         ret += x/gmpAss6[i];

     return ret;

 }

 ll assp7(ll x)

 {

     ll ret = ;

     for (int i=; i<=gmpAss7[]; i++)

         if (gmpAss7[i]) ret += x/gmpAss7[i];

     return ret;

 }

 void makeAss5()

 {

     for (int i=, ass=; i<(<<(ass)); i++)

     {

         ll dt = , lst = , del;

         for (int j=, t=i; j<=ass; j++, t>>=)

             if (t&){

                 ++dt, del = gcd(lst, ass5[j]);

                 lst *= ass5[j]/del;

             }

         gmpAss5[i] = (dt&)?lst:-lst;

     }

 }

 void makeAss6()

 {

     for (int i=, ass=; i<(<<(ass)); i++)

     {

         ll dt = , lst = , del;

         for (int j=, t=i; j<=ass; j++, t>>=)

             if (t&){

                 ++dt, del = gcd(lst, ass6[j]);

                 lst *= ass6[j]/del;

             }

         gmpAss6[i] = (dt&)?lst:-lst;

     }

 }

 void makeAss7()

 {

     ll &tot = gmpAss7[];

     for (int i=, ass=; i<(<<(ass)); i++)

     {

         ll dt = , lst = , del;

         for (int j=, t=i; j<=ass; j++, t>>=)

             if (t&){

                 ++dt, del = gcd(lst, ass7[j]);

                 lst *= ass7[j]/del;

             }

         lst = (dt&)?lst:-lst;

         bool chk = ;

         for (int i=; i<=tot&&chk; i++)

             if (gmpAss7[i]==-lst) gmpAss7[i] = , chk = ;

         if (chk) gmpAss7[++tot] = lst;

     }

 }

 ll calc(ll x, ll k)

 {

     ll ret = ;

     if (k==) return x;

     if (k==) return x>>;

     if (k==) return (x/+x/-x/);

     if (k==) return (x/+x/+x/-x/-x/-x/+x/);

     if (k==) return assp5(x);

     if (k==) return assp6(x);

     if (k==) return assp7(x);

     return ret;

 }

 void write(ll x){if (x/) write(x/);putchar(x%+'');}

 int main()

 {

     makeAss5(), makeAss6(), makeAss7();

     for (scanf("%d",&T); T; --T)

     {

         l = read(), r = read(), k = read();

         write(calc(r, k)-calc(l-, k)), putchar('\n');

     }

     return ;

 }

END

巴特西

【数学技巧】divisor

题目大意

题目分析

最新文章

热门文章

巴特西

【数学 技巧】divisor

题目大意

题目分析

最新文章

热门文章

【数学技巧】divisor