题目概述:
给定了函数f的表达式与函数g的表达式，给了T（T<=100）次询问，每次询问一个数n(n<=1e12),求g(n)的值，最终答案对1e9+7取模。
tag:
记忆化,递归,数学
题解:
首先我们需要知道取模的常识:
1. (a+b)%mod=(a%mod+b%mod)%mod
2. a*b%mod=a%mod*b%mod
3. (a+b)%mod=(a+b+mod)%mod（这个很重要，因为在取模过程中，即便是sum原本是累加的，其本身数值比a大，但是经过取模之后，sum可能小于a，因而，当计算(sum-a)%mod的时候就需要写成(sum-a+mod)%mod来避免这种出现负数的情况）
我们首先考虑 f(x) 怎么计算,我们可以很容易地写出:
但是，写过递归的都知道，这将会产生一棵二叉树，我们粗略的估计他的计算次数
假如 f(x)=f(x/3)+f(x/3)，那么我们只有在算到x=0的时候才会抵达递归出口，这棵二叉树的深度就大概是log(3)x,而这是一棵类似于满二叉树的树，除了最后一层外的每一层的点都会被填满，那么当n=1e12的时候，树的深度是12log(3)10，约等于25，那么我们就需要计算pow(2,25)次，而原表达式的复杂度肯定是更高的。不是，查询100次f(n)我就gg了，那还写个集贸啊？
我们以计算 f(6)为例，观察下图，我们就会发现f(1)被计算了多次，而当n越大，我们重复计算的就越多，实际上，不管是不断除以2还是不断除以3，一个数n顶多计算log2(n)次和log3(n)次，如果不重复计算的话，我们计算f(n)的时间复杂度肯定是要小于log2(n)+log3(n)的。所以，为了避免重复的计算我们便需要对其记忆化。
修正代码:
这样的话，计算过的数值就不会重复计算了
f(n)的问题解决了，那么我们就可以去解决g(n)了，g(n)是个求和，而求和本身的时间复杂度就是O(n)的，我们使用强硬的手段必然会T飞掉。由于表达式本身的复杂度有问题，我们就要去想想如何对表达式进行进一步的简化，我们可以带入f(x)=f(x/2)+f(x/3)。步骤如下:
在得到了这个式子之后我们会发现，g(x)与f(x)递归式表达式的区别也就在于多了点杂项，但是，即便每次都要计算杂项，对于每一项的计算也都是log的，而实际的复杂度也只是Alog(n) (这里的A是个小常数),具体写法参见AC代码。
AC代码:
