100分求一个质数组合个数的算法

有K+1个自然数，其中最后一个为数固定为L。前K个数的大小不超过L，并且可以重复出现。怎么计算这K个数为互质（不是两两互质）数的组合有多少种。K<=10,L<=10000。计算机应该怎么编程实现，给出算法也可以，不需要输出组合，只需要组合的个数。
如：K＝2；L＝4的组合有12种。如（1 1 4,1 2 4,1 3 4，1 4 4,2 1 4，2 3 4，3 1 4，3 2 4，3 3 4，3 4 4, 4 1 4，4 3 4）
或：K＝2,L＝36。其中（10 15 36）不是两两互质，但三个数互质也算一种。
求那位兄弟姐妹指导一下小弟，谢谢！

递归前K个数互质的情况。
F(k) = g(L)*F(k-1)

不太明白，能否具体一点。