TCO 2015 Round 2A DIV1

ModModMod 傻逼数论

题意：

这是一道卖萌的题。。给你一个取模序列$m$，令$f(x)=(\cdots (x\ mod\ m[0])\ mod m[1])\mod m[2]\cdots $，问你$\sum_{i=1}^R f(i)$的值是多少

题解：

容易知道一点，若$i<j$且$m[i]\le m[j]$，那么$m[j]$就是没有意义的，所以首先将m变成递减序列。接下来观察每次取模后的结果，由于是从1到R，所以序列第一次取模后会变成：

$$(0+1+2+\cdots+m[0]-1)+(0+1+2+\cdots+m[0]-1)+\cdots+(0+1+2+\cdots+m[0]-1)+(0+1+2+\cdots+R\ mod\ m[0])$$

其中$0+1+2+\cdots+m[0]-1$一共有$R/m[0]$个，由于$f(0)=0$，所以这样就变成了和原问题一样的子问题了，递归求解即可。

代码：

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

vector<int> v;

long long dfs(int i,int x) {

    if (x == )return ;

    if (i == v.size())return ( + x) * x / ;

    return x / v[i] * dfs(i + , v[i] - ) + dfs(i + , x % v[i]);

}

class ModModMod{

public:

    long long findSum(vector <int> m, int R){

        v.push_back(m[]);

        for(int i=;i<m.size();i++)

            if(v[v.size()-]>m[i])

                v.push_back(m[i]);

        return dfs(,R);

    }

};