自建站排名,石家庄外贸建站公司,免费网站app,软件定制开发公司嘟嘟嘟 感觉这几道数论题都差不多#xff0c;但这到明显是前几道的升级版。 推了一大顿只能得60分#xff0c;不得不看题解。 各位看这老哥的题解吧 我就是推到他用\(T\)换掉\(kd\)之前#xff0c;然后枚举\(T\)的。这个转换确实想不出来啊。 还有最后一句#xff0c;最终的… 嘟嘟嘟 感觉这几道数论题都差不多但这到明显是前几道的升级版。 推了一大顿只能得60分不得不看题解。 各位看这老哥的题解吧 我就是推到他用\(T\)换掉\(kd\)之前然后枚举\(T\)的。这个转换确实想不出来啊。 还有最后一句最终的式子\[\sum_{T 1} ^ {n} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor * \sum_{k | T} \mu(\frac{T}{k}) (k \in prime)\] 他把后面的那个sum预处理了。令\(f(T) \sum_{k | T} \mu(\frac{T}{k}) (k \in prime)\)由此可见这个函数的自变量是\(T\)而预处理的时候是枚举\(T\)的质因数累加得到\(f(T)\)跟埃氏筛法很像。 #includecstdio
#includeiostream
#includecmath
#includealgorithm
#includecstring
#includecstdlib
#includecctype
#includevector
#includestack
#includequeue
using namespace std;
#define enter puts()
#define space putchar( )
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF 0x3f3f3f3f;
const db eps 1e-8;
const int maxn 1e7 5;
inline ll read()
{ll ans 0;char ch getchar(), last ;while(!isdigit(ch)) last ch, ch getchar();while(isdigit(ch)) ans (ans 1) (ans 3) ch - 0, ch getchar();if(last -) ans -ans;return ans;
}
inline void write(ll x)
{if(x 0) x -x, putchar(-);if(x 10) write(x / 10);putchar(x % 10 0);
}int v[maxn], prm[maxn], mu[maxn];
ll f[maxn], sum[maxn];
void init()
{mu[1] 1;for(int i 2; i maxn; i){if(!v[i]) v[i] i, prm[prm[0]] i, mu[i] -1;for(int j 1; j prm[0] i * prm[j] maxn; j){v[i * prm[j]] prm[j];if(i % prm[j] 0) {mu[i * prm[j]] 0; break;}else mu[i * prm[j]] -mu[i];}}for(int i 1; i prm[0]; i)for(int j 1; prm[i] * j maxn; j)f[prm[i] * j] mu[j];for(int i 1; i maxn; i) sum[i] sum[i - 1] f[i];
}ll solve(int n, int m)
{int Min min(n, m);ll ret 0;for(int l 1, r; l Min; l r 1){r min(n / (n / l), m / (m / l));ret (sum[r] - sum[l - 1]) * (n / l) * (m / l);}return ret;
}int main()
{init();int T read();while(T--){ll n read(), m read();write(solve(n, m)), enter;}return 0;
} 转载于:https://www.cnblogs.com/mrclr/p/10112023.html
