2020ICPC江西省大学生程序设计竞赛（A,B,E,G,H,I,K,L,M）
judge: 牛客
A-A Simple Math Problem
judge:牛客
题意
给你一个n，让你求出\(\sum_{i=1}^{n}\sum_{j=1}^{i}[gcd(i,j)==1]f(j)\)。
其中f(x)表示的是数位和，eg:f(122)=1+2+2=5。
题解
一眼可以看出是道反演题，但是仔细想想发现不是特别好维护，然后给的范围又有点误导，让人以为可以瞎搞过（实际上真的可以打表过或者容斥过），然后中间耽搁了很长时间，还写了个瞎搞的做法，不过没敢交，最后才发现转换一下就是一道经典的反演题。
首先题目让我们求的是\(\sum_{i=1}^{n}\sum_{j=1}^{i}[gcd(i,j)==1]f(j)\)，我们需要转换成\(\sum_{i=1}^{n}f(i)\sum_{j=i+1}^{n}[gcd(i,j)==1]\)。
其实只是枚举策略的变换，求的答案还是一样，只不过第二个公式可以用反演求，而且还比较好求，第一个没有办法用反演做（其实是我不会）。
至于原因，我们需要对第一个公式有足够的了解，第一个公式让我们求的是所有比当前数小，且与当前数互质的数的数位和。
思维转换一下，我们把每个数单独进行考虑，每个数对答案产生的贡献就是比它大，且与它互质的数的个数乘以这个数的数位和（就是转换后的公式）。
至于第二个公式怎么求，可以参考我写的一篇题解，这个题让我们求的就是前半部分，只不过数位和变成了数位乘。
代码
#include
#define PI atan(1.0)*4
#define rp(i,s,t) for (int i = (s); i <= (t); i++)
#define RP(i,t,s) for (int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define pii pair
#define pll pair
#define pil pair
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int N = 1e6+7;
int n;
ll phi[N],mu[N];
int prime[N];
int flag[N];
ll F[N];
ll G[N];
ll Num[N];
int num=0;
int f(int x){
int ans=0;
while(x) ans+=x%10,x/=10; return ans;
}
int g(int x){
int ans=1;
while(x) ans*=x%10,x/=10;
}
void init(){
phi[1]=1;
mu[1]=1;
F[1]=G[1]=1;
for (int i=2;i<=n;i++){
F[i]=f(i);
G[i]=g(i);
if (flag[i]==0)//这代表i是质数
{
prime[++num]=i;
phi[i]=i-1;
mu[i]=-1;
}
for (int j=1;j<=num&&prime[j]*i<=n;j++){
flag[i*prime[j]]=1;
if (i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
mu[i*prime[j]]=0;
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1),mu[i*prime[j]]=-mu[i]; }
}
rp(i,1,n) for(int j=i;j<=n;j+=i) Num[i]+=F[j];
}
void solve(){
n=read();
init();
