### 题目描述

#### 输入输出

##### 输出格式

T行，每行一个整数表示第i组数据的结果

#### 样例

##### 输入
2
10 10
100 100
##### 输出
30
2791

### 代码

#include
#define maxn 10001000
#define ll long long
using namespace std;
bool vis[maxn];
ll s[maxn];
int pri[maxn],top;
int mu[maxn],g[maxn];
void Init(int n){
mu[1]=1;
for (int i=2;i<=n;++i){
if (!vis[i]) mu[i]=-1,pri[++top]=i;
for (int j=1;j<=top&&pri[j]*i<=n;++j){
vis[i*pri[j]]=1;
if (i%pri[j]==0) break;
mu[pri[j]*i]=-mu[i];
}
}
for (int j=1;j<=top;j++)
for (int i=1;i*pri[j]<=n;i++)
g[i*pri[j]]+=mu[i];
for (int i=1;i<=n;i++)
s[i]=s[i-1]+(ll)g[i];
}
int main(){
ios::sync_with_stdio(false);
Init(maxn-1);
int T;cin>>T;while(T--){
int n,m;
cin>>n>>m;
if (n>m) swap(n,m);
ll ans=0;
for (int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans+=(ll)(n/l)*(m/l)*(s[r]-s[l-1]);
}
cout<
 
 Share Topic Selected Show Comments 【学习笔记】AC 自动机 听老师说 AC 自动机不算自动机啊，因为 Wikipedia 上的说法也是 $Aho–Corasick algorithm$ 而不是 $Aho–Corasick… 11 Aug 2018 【2018 HDU 多校 Contest 6 / 6363】Bookshelf / 题解 题目描述 你有$N$本书和一个$K$层的书架。 随机地将$N$本书放进书架，这个时候第$i$层的书本数量为… 08 Aug 2018       Topics Thought: 30 Study: 26 Selected: 26 Zepto's © 2022 Sponsor Data & privacy Contact → Published with Ghost • Theme Attila • System theme  $(document).ready(function () { var viewport = $(window); var post =$('.post-content'); // Responsive videos with fitVids post.fitVids(); // Format code blocks and add line numbers function codestyling() { $('pre code').each(function(i, e) { // Code highlight hljs.highlightBlock(e); // No lines for plain text blocks if (!$(this).hasClass('language-text')) { var code = $(this); // Calculate amount of lines var lines = code.html().split(/\n(?!$)/g).length; var numbers = []; if (lines > 1) { lines++; } for (i = 1; i < lines; i++) { numbers += '<span class="line" aria-hidden="true">' + i + '</span>'; } code.parent().append('<div class="lines">' + numbers + '</div>'); } }); } codestyling(); // Reading progress bar on window top function readingProgress() { var postBottom = post.offset().top + post.height(); var viewportHeight = viewport.height(); var progress = 100 - (((postBottom - (viewport.scrollTop() + viewportHeight) + viewportHeight / 3) / (postBottom - viewportHeight + viewportHeight / 3)) * 100); $('.progress-bar').css('width', progress + '%'); (progress > 100) ?$('.progress-container').addClass('complete'): $('.progress-container').removeClass('complete'); } readingProgress(); // Trigger reading progress viewport.on({ 'scroll': function() { readingProgress(); }, 'resize': function() { readingProgress(); }, 'orientationchange': function() { readingProgress(); } }); // Check if disqus is defined by code injection if (typeof disqus === 'undefined') { // hide comment section$('.post-comments').css({ 'display': 'none' }); } else { $('#show-disqus').on('click', function() {$.ajax({ type: "GET", url: "//" + disqus + ".disqus.com/embed.js", dataType: "script", cache: true }); \$(this).parent().addClass('activated'); }); } });